数据结构--排序
目录
正文开始：
1. 排序的概念及应用
1.1 概念
排序：所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
1.2 应用
购物筛选排序
院校排名
1.3 常见算法排序
2. 排序算法实现
2.1 插入排序
基本思想：
直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。如下图所示：
2.1.1 直接插入排序
当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移。
代码编写：
void InsertSort(int* a, int n) { //[0, n-1] for (int i = 0; i < n - 1; i++) { //[0, n-2]是最后一组 //[0, end]有序，end+1位置的值插入[0, end]，保持有序 int end = i; int tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = tmp; } }直接插入排序特性总结：
- 元素集合越接近有序，直接插⼊排序算法的时间效率越⾼
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
2.1.2 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进行排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。即先进行预排序将数组解决有序，再进行插入排序。
它是在直接插⼊排序算法的基础上进行改进而来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。
代码编写：
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) //gap>1是预排序，gap=1是插入排序 { //推荐写法：除3 gap = gap / 3 + 1; //加1是为了保证最后一次gap为1 //多组并着走 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } InserSort(a, n); }希尔排序特性总结：
- 希尔排序是对直接插⼊排序的优化。
- 当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序 的了，这样就会很快。这样整体而言，可以达到优化的效果
2.2 选择排序
选择排序的基本思想：
每⼀次从待排序的数据元素中选出最小（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
2.2.1 直接选择排序
- 在元素集合array[ i ]--array[ n - 1 ]中选择关键码最大（小）的数据元素
- 若它不是这组元素中的最后一个（第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的array[ i ]--array[ n-2 ]（array[ i+1 ]--array[ n-1 ] ）集合中，重复上述步骤，直到集合剩余1个元素
代码实现：
此处代码的实现，采取遍历一遍找出两个数，一个最小的数放置在begin位置，一个最大的数放置在end位置，然后begin++; end--; 随后再接着遍历一遍找出次小的和次大的数依次放置在新的begin和end位置，随后依次类推直至结束。
//直接选择排序 void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int mini = begin; int maxi = begin; for (int i = begin; i <= end; i++) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } //最小的数换到最左边 Swap(&a[mini], &a[begin]); if (begin == maxi) { maxi = mini; } //最大的数换到最又边 Swap(&a[maxi], &a[end]); ++begin; --end; } }
直接选择排序特性总结：
- 直接选择排序思考⾮常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度： O(N² )
- 空间复杂度： O(1)
2.2.2 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建小堆。此处不再赘述，点击可跳转到代码详解处
2.3 交换排序
交换排序基本思想：
所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较⼤的记录向序列的尾部移动，键值较⼩的记录向序列的前部移动
2.3.1 冒泡排序
冒泡排序是⼀种最基础的交换排序。之所以叫做冒泡排序，因为每⼀个元素都可以像小⽓泡⼀样，根据自身大小⼀点⼀点向数组的⼀侧移动
代码实现：
//冒泡排序 void BubbleSort(int* a, int n) { int exchange = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { exchange = 1; swap(&a[j], &a[j + 1]); } } if (exchange == 0) { break; } } }冒泡排序特性总结：
- 时间复杂度： O(N²)
- 空间复杂度： O(1)
2.3.2 快速排序！！！
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均⼩于基准值，右子序列中所有元素均⼤于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为⽌。
快速排序实现主体框架：
//快速排序 void QuickSort(int* a, int left, int right) { if (left >= right) { return; } //_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分 int meet = _QuickSort(a, left, right); QuickSort(a, left, meet - 1); QuickSort(a, meet + 1, right); }将区间中的元素进⾏划分的 _QuickSort ⽅法主要有以下几种实现方式：
1. hoare版本
从右边开始找比keyi小的值，从左边开始找比keyi大的值
代码实现：
void QuickSort(int* a, int left, int right) { if (left >= right) { return; } int keyi = left; int begin = left; int end = right; while (begin < end) { //右边找小 while (begin < end && a[end] >= a[keyi]) { --end; } //左边找大 while (begin < end && a[begin] <= a[keyi]) { ++begin; } Swap(&a[begin], &a[end]); } Swap(&a[keyi], &a[begin]); keyi = begin; //[left, keyi-1] keti [keyi+1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }此方法在有序的情况下存在栈溢出的风险（因为递归的深度太深导致）和效率退化问题
为避免有序情况下的效率退化问题，可采取三数选中的方式来选择keyi的值，即选择既不是最大也不是最小的中间值做keyi的值，如下所示：
//三数取中 int GetMidi(int* a, int left, int right) { int midi = (left + right) / 2; // left midi right if (a[left] < a[midi]) { if (a[midi] < a[right]) { return midi; } else if (a[left] < a[right]) { return right; } else { return left; } } else // a[left] > a[midi] { if (a[midi] > a[right]) { return midi; } else if (a[left] < a[right]) { return left; } else { return right; } } }此时快排还是存在一个缺陷：即当递归进行到后面，到了对最后5个数进行上述方法递归排序的时候会发现，对仅仅5个数进行排序，却整整要进行7此递归调用，而这递归期间还存在对其进行分割等操作，效率非常低。可进行小区间优化，优化如下所示：
void QuickSort(int* a, int left, int right) { if (left >= right) { return; } //小区间优化，不再递归分割，减少递归次数 if ((right - left + 1) < 10) { InsertSort(a + left, right - left + 1); } else { //三数取中 int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]); int keyi = left; int begin = left; int end = right; while (begin < end) { //右边找小 while (begin < end && a[end] >= a[keyi]) { --end; } //左边找大 while (begin < end && a[begin] <= a[keyi]) { ++begin; } Swap(&a[begin], &a[end]); } Swap(&a[keyi], &a[begin]); keyi = begin; //[left, keyi-1] keti [keyi+1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } }问题1：怎么做到相遇位置比key值小？
答：
2. 挖坑法
思路：
创建左右指针。首先从右向左找出比基准小的数据，找到后立即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）
int _QuickSort1(int* a, int left, int right) { int mid = a[left]; int hole = left; int key = a[hole]; while (left < right) { while (left < right && a[right] >= key) { --right; } a[hole] = a[right]; hole = right; while (left < right && a[left] <= key) { ++left; } a[hole] = a[left]; hole = left; } a[hole] = key; return hole; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = _QuickSort1(a, left, right); // [left, keyi-1] keyi [keyi+1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }3. lomuto前后指针法
创建前后指针，从左往右找⽐基准值小的进⾏交换，使得小的都排在基准值的左边。
- 初始时，prev指针指向序列开头，cur指针指向prev指针的后一个位置
- 然后判断cur指针指向的数据是否小于key，若小于，则prev指针后移一位（即prev指针++），并且cur指向的内容与prev指向的内容交换，然后cur指针++
- cur指针指向的数据仍然小于key，步骤相同
- 此时cur指针指向的内容大于key，则cur指针继续++
- cur指针指向的数据小于key，prev先后移一位，然后与cur指向的数据交换，cur再++
- 再比较，cur指针指向的数据还是小于key，prev先后移一位，然后与cur指向的数据交换，cur再++
- 又一次比较，cur指针指向的数据还是小于key，prev先后移一位，然后与cur指向的数据交换，cur++
- cur再次与key比较，大于key，cur指针后移
- cur还是比key大，cur继续后移
- 此时cur指针已经越界，这时我们将prev指向的内容与kry进行交换
- 结束，此时key左边的数据都比key小，key右边的数据都比key大
int _QuickSort2(int* a, int left, int right) { int prev = left, cur = left + 1; int key = left; while (cur <= right) { if (a[cur] < a[key] && ++prev != cur) //后一项是为了防止自己和自己交换 { swap(&a[cur], &a[prev]); } ++cur; } swap(&a[key], &a[prev]); return prev; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = _QuickSort2(a, left, right); // [left, keyi-1] keyi [keyi+1, right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }4. 非递归版本的快排
因为递归版本会存在当递归深度太深时，存在栈溢出的风险，所以此处再介绍一种非递归版本的快排。
非递归版本的快速排序需要借助数据结构：栈
#include"Stack.h" void QuickSortNonR(int* a, int left, int right) { ST st; STInit(&st); STPush(&st, right); STPush(&st, left); while (!STEmpty(&st)) { int begin = STTop(&st); STPop(&st); int end = STTop(&st); STPop(&st); int keyi = _QuickSort2(a, begin, end); // [begin, keyi-1] keyi [keyi+1, end] if (keyi + 1 < end) { STPush(&st, end); STPush(&st, keyi+1); } if (begin < keyi-1) { STPush(&st, keyi-1); STPush(&st, begin); } } STDestroy(&st); }循环每走一次，相当于一次递归，取栈顶区间，单趟排序完了之后，先右再左进行子区间入栈
2.4 归并排序
归并排序算法思想：
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide and Conquer）的⼀个非常典型的应⽤。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 归并排序核⼼步骤：
// 时间复杂度：O(N*logN) // 空间复杂度：O(N) void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin >= end) return; int mid = (begin + end) / 2; // 如果[begin, mid][mid+1, end]有序就可以进行归并了 _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid + 1, end); // 归并 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //memcpy需包含string.h头文件 memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp = NULL; }
非递归版：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } // gap每组归并数据的数据个数 int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { // [begin1, end1][begin2, end2] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2); // 第二组都越界不存在，这一组就不需要归并 if (begin2 >= n) break; // 第二的组begin2没越界，end2越界了，需要修正一下，继续归并 if (end2 >= n) end2 = n - 1; int j = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } printf("\n"); gap *= 2; } free(tmp); tmp = NULL; }2.5 非比较排序
2.5.1 计数排序
计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
// 时间复杂度:O(N+range) // 只适合整数/适合范围集中 // 空间范围度：O(range) void CountSort(int* a, int n) { int min = a[0], max = a[0]; for (int i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } int range = max - min + 1; //printf("%d\n", range); int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { perror("calloc fail"); return; } // 统计次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } // 排序 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } free(count); }2.6 排序算法复杂度及稳定性分析
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[ i ] = r[ j ]，且 r[ i ] 在 r[ j ] 之前，⽽在排序后的序列中，r[ i ]仍在r[ j ]之前，则称这种排序算法是稳定的；否则称为不稳定的
