一、插入排序
步骤：
- 从第一个元素开始，该元素可以认为已经被排序
- 取下一个元素tem，从已排序的元素序列从后往前扫描
- 如果该元素大于tem，则将该元素移到下一位
- 重复步骤3，直到找到已排序元素中小于等于tem的元素
- tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
- 重复步骤2~5
动态展示过程如下：
思路：
- 在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
- 但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
代码实现如下：
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; //数组在[0, end]是有序的 while (end >= 0) { if (a[end + 1] < a[end])//升序 { Swap(&a[end], &a[end + 1]); end--; } else break; } } }
时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
二、希尔排序
步骤：
- 先选定一个小于N的整数gap作为分组数量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…一般我们选择每次分组数量为上次的1/3。
- 当分组的数量（gap）减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
动态展示过程如下：
分解战术如下（颜色相同为一组）：
思路：希尔排序，先将待排序列进行预排序，使待排序列接近有序，然后再对该序列进行一次插入排序，此时插入排序的时间复杂度为O(N)，
代码实现如下：
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1;//最后一次为1（大于1时为预排序，等于1为插入排序） for (int i = 0; i < n - gap; i++)//插入排序变式（分成gap组，每组插入排序) { int end = i; while (end >= 0) { if (a[end + gap] < a[end])//升序 { Swap(&a[end], &a[end + gap]); end -= gap; } else break; } } } }
时间复杂度平均：O(N^1.3)
空间复杂度：O(1)
三、选择排序
思路：
每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
动态展示过程如下：
代码实现如下：
void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int min = begin, max = end; for (int i = begin; i < end; i++) { if (a[i] < a[min]) min = i; if (a[i] > a[max]) max = i; } if (min == end) { Swap(&a[begin], &a[min]); Swap(&a[end], &a[max]); } else { Swap(&a[end], &a[max]); Swap(&a[begin], &a[min]); } begin++, end--; } }
时间复杂度：最坏情况：O(N^2)
最好情况：O(N^2)
空间复杂度：O(1)
四、堆排序
在前面的堆与二叉树章节讲过，在此就不再赘述。
void AdjustDown(int* a, int n, int root) { int child = root * 2 + 1; while (child < n) { if (child + 1 < n && a[child] < a[child + 1])//建大堆 { child++; } if (a[root] < a[child])//建大堆 { Swap(&a[child], &a[root]); root = child; child = root * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { for (int i = ((n - 1) - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } for (int i = 1; i < n; i++) { Swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); } }
五、冒泡排序
void BubbleSort(int* a, int n) { for (int i = 0; i < n; i++) { int flag = 0; for (int j = 1; j < n - i; j++) { if (a[j - 1] > a[j]) { Swap(&a[j], &a[j - 1]); flag = 1; } } if (flag == 0) break; } }
六、快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的任一元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：
6.1 hoare版本
- 思路：
- 选出一个key，一般是最左边或是最右边的。
- 定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
- 在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
- 此时key的左边都是小于key的数，key的右边都是大于key的数
- 将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序。
单趟动图展示如下：
【补】快速排序的优化：
法1：三数取中法选基准值key（三数取中）
法2：递归到小的子区间时，可以考虑使用插入排序（小区间优化）
三数取中代码：
int GetMid(int* a, int left, int right) { int midi = (left + right) / 2; if (a[left] < a[midi]) { if (a[midi] < a[right]) return midi; else if (a[left] < a[right])//midi最大，二人取大为中 return right; else return left; } else //a[left] > a[midi] { if (a[midi] > a[right]) return midi; else if (a[left] < a[right])//midi最小，二人取小为中 return left; else return right; } }
小区间优化代码：
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; //数组在[0, end]是有序的 while (end >= 0) { if (a[end + 1] < a[end])//升序 { Swap(&a[end], &a[end + 1]); end--; } else break; } } }
【ps】左边作key，right先走，相遇位置的值一定比基准值小，或相遇位置就是key的位置
Q：为什么相遇位置的值一定比基准值小，或者相遇位置就是key？
A：第一种情况：R找到小，但L找大没找到，这时L会遇到R；第二种情况：R找小没找到，直接遇到L，此时要么是一个比key小的位置，要么直接到key。类似地，若右端作key，则让L先走，相遇位置值就比key大。
代码示例如下：
int PartSort1(int* a, int left, int right) { //三数取中 int midi = GetMid(a, left, right); Swap(&a[midi], &a[left]); int begin = left, end = right; int key = left; while (begin < end) { while (begin < end && a[end] >= a[key]) end--; while (begin < end && a[begin] <= a[key]) begin++; Swap(&a[begin], &a[end]); } Swap(&a[key], &a[begin]); return begin; }
6.2 挖坑法
挖坑法是后人基于Hoare版本实现的改进版。
拿走key的值，留下一个坑位。right下标指针找小，找到后将值填到该坑位上，并留下一个新坑位；left下标指针找大，找到后将值填到新坑位上，且再留下一个坑，以此往复。
直到left与right相遇，就将key的值填到 left == right 的坑位。
代码示例如下：
int PartSort2(int* a, int left, int right) { //三数取中 int midi = GetMid(a, left, right); Swap(&a[midi], &a[left]); int begin = left, end = right; int key = a[left]; int flag = left; while (begin < end) { while (begin < end && a[end] >= key) end--; a[flag] = a[end]; flag = end; while (begin < end && a[begin] <= key) begin++; a[flag] = a[begin]; flag = begin; } a[begin] = key; return begin; }
6.3 前后指针法
对于前指针prev（左）、后指针cur（右）、基准值key（数组头部），若cur找到比key小的值，则++prev，cur与prev位置的值交换；若cur找到比key大的值，则++cur。相当于把比key大的值翻转到右边（大的值往右边运），比key小的值翻转到左边（把小的值往左边运）。
【ps】prev要么紧跟cur（即prev的下一个位置就是cur/prev紧跟在比key大的值后面），要么跟cur中间间隔着一段由比key大的值组成的区间。
代码示例如下：
int PartSort3(int* a, int left, int right) { int prve = left, cur = left + 1; int key = a[left]; while (cur <= right) { if (prve < cur && a[cur] <= key) { prve++; Swap(&a[prve], &a[cur]); } cur++; } Swap(&a[left], &a[prve]); return prve; } 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 key = PartSort1(a, left, right); //int key = PartSort2(a, left, right); int key = PartSort3(a, left, right); QuickSort(a, key + 1, right); QuickSort(a, left, key - 1); } }
6.4 非递归实现
用栈实现（关于栈的完整代码和更多解释，详见 探索数据结构：栈的实现方法）。
先将所有数据组成的区间端点端点值入栈，然后，每次从栈里取一段区间的端点值（首次是所有数据组成的区间）进行单趟的排序；单趟排序中，被划分的子区间分别入栈（因为栈的特点是后进先出，所以右先入左后入才能使序列跟入栈前保持一致）；直到划分的子区间只有一个值或子区间不存在就不再入栈。
代码实现：
int PartSort(int* a, int left, int right) { int midi = GetMid(a, left, right); if (midi != left) Swap(&a[midi], &a[left]); int prev = left, cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; } void QuickSortNonR(int* a, int left, int right) { ST st; StackInit(&st); //先入右值（尾部的值），再入左值（头部的值） StackPush(&st, right); StackPush(&st, left); while (!StackEmpty(&st)) { //先出左值，再出右值 int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); //进行单趟的排序，且记录排序后的基准值下标 int keyi = PartSort(a, begin, end); //分出区间：[begin,keyi-1] keyi [keyi+1, end] //并分别入栈 if (keyi + 1 < end) //先入右区间 { StackPush(&st, end); //先入右值 StackPush(&st, keyi + 1); //再入左值 } if (begin < keyi - 1) //再入左区间 { StackPush(&st, keyi - 1); //先入右值 StackPush(&st, begin); //再入左值 } } StackDestroy(&st); }
七、归并排序
7.1 递归实现
归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
- 将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
- 将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。
动画展示：
代码实现：
void _MergeSort(int* arr, int left, int right, int* temp) { //分解： //分割数组只有一个元素时停止递归 if (left >= right) { return; } int mid = (left + right) / 2; _MergeSort(arr, left, mid, temp); //分割并排序数组左半边 _MergeSort(arr, mid + 1, right, temp); //分割并排序数组右半边 //合并： int begin1 = left, end1 = mid; //数组1的左右区间 int begin2 = mid + 1, end2 = right; //数组2的左右区间 int i = begin1; //排序两个有序数组 while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { temp[i] = arr[begin1]; begin1++; } else { temp[i] = arr[begin2]; begin2++; } i++; } while (begin1 <= end1) { temp[i] = arr[begin1]; begin1++; i++; } while (begin2 <= end2) { temp[i] = arr[begin2]; begin2++; i++; } //拷贝临时数组的内容到原数组（可以调用memcpy函数） //memcpy(arr+left, temp+left, (right-left+1)*sizeof(int)); for (i = left; i <= right; i++) { arr[i] = temp[i]; } } void MergeSort(int* arr, int size) { int* temp = (int*)malloc(size * sizeof(int)); if (temp == NULL) { perror("malloc fail\n"); return; } _MergeSort(arr, 0, size - 1, temp); //归并排序的过程 free(temp); temp = NULL; }
7.2 非递归实现
7.2.1 思路实现
通过循环实现。将从同一组中分出的两个数据进行比较，按大小（升序）合并为一个有序区间。
将待排序的序列不断二分，直至二分的结果为单个数据，接着，将从同一组中分出的两个数据进行比较，按大小顺序一一归并为一个有序（升序）区间；归并后，重新排序，再对有序区间进行二二归并（每个有序区间有两个数据），然后是四四归并（每个有序区间有四个数据）......以此类推，直至待排序的序列整体有序。
而对于两个有序区间的归并，同样要开辟一个新的临时数组来存排好序的数据，最后，将排好序的序列整体拷贝回原数组。
7.2.2 数组边界问题
在归并排序的非递归实现中，我们要遍历数组，将两个长度为gap的数组排序合并，但是gap总是2的幂次方，这就导致数组长度不一定是 gap*2 的倍数，这就导致两个数组在遍历到数组边界时会导致越界问题。所以我们要对数组的边界问题进行处理
1. 第一个数组越界
黄色和蓝色数组是需要合并的两个数组，第一个数组指的是黄色数组，第二个数组指的是蓝色数组
此时遍历到数组末尾时，第一个数组只有一个元素，但是需要合并的数组长度是2，所以第一个数组访问时会造成越界（第二个数组自然也越界）
2. 第二个数组全部越界
此时遍历到数组末尾时，第一个数组的长度刚好到原数组的末尾，第二个数组不存在，访问第二个数组是会越界
3. 第二个数组部分越界
此时第一个数组在数组内，第二个数组只有一部分在数组内，第二个数组存在但是长度没有gap，访问第二个数组时会越界
解决方法 ：
我们来解决这些数组越界问题的方法是调整数组区间范围：
- 第一个数组越界时，第二个数组不存在，所以不用合并，第一个数组本身就是有序数组
- 第二个数组完全越界时，第二个数组依然不存在，所以不用合并
- 第三个数部分组越界时，第二个数组存在但是不完整，此时我们将第二个数组的结束位置调整为原数组末尾位置即可，让第一个数组和第二个数组合并。
代码示例：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail\n"); return; } //（单趟）一一归并 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; //修正边界 //归并一部分，拷贝一部分 if (end1 >= n || begin2 >= n) { break;//第一个区间或第二个区间越界就不拷贝 } if (end2 >= n) { end2 = n - 1;//第二个区间越界就修正区间边界end2 } //依次比较两个区间相同下标位置的值，并按序放入临时数组 int j = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j] = a[begin1]; j++, begin1++; } else { tmp[j] = a[begin2]; j++, begin2++; } } //没走完的区间继续归并 while (begin1 <= end1) { tmp[j] = a[begin1]; j++, begin1++; } while (begin2 <= end2) { tmp[j] = a[begin2]; j++, begin2++; } //归并一部分，拷贝一部分 memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } //一一归并 => 二二归并 => 四四归并 => ... gap *= 2; } free(tmp); }
八、计数排序
计数排序的作用是，按照大小顺序排列每个数据，并保留每个数据重复出现的次数。它又称为鸽巢原理，是对哈希直接定址法的变形应用。实现它的基本步骤为：1. 统计相同元素出现次数；2. 根据统计的结果将序列回收到原来的序列中。
详解算法：
先假设 20 个数列为：{9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9}。
让我们先遍历这个无序的随机数组，找出最大值为 10 和最小值为 0。这样我们对应的计数范围将是 0 ~ 10。然后每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。
比如第一个整数是 9，那么数组下标为 9 的元素加 1，如下图所示。
第二个整数是 3，那么数组下标为 3 的元素加 1，如下图所示。
继续遍历数列并修改数组......。最终，数列遍历完毕时，数组的状态如下图。
数组中的每一个值，代表了数列中对应整数的出现次数。
有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。比如统计结果中的 1 为 2，就是数列中有 2 个 1 的意思。这样我们就得到最终排序好的结果。
0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10
动画展示：
贴别说明：
虽然计数排序看上去很强大，但是它存在两大局限性：
1.当数列最大最小值差距过大时，并不适用于计数排序
比如给定 20 个随机整数，范围在 0 到 1 亿之间，此时如果使用计数排序的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。
2.当数列元素不是整数时，并不适用于计数排序
如果数列中的元素都是小数，比如 3.1415，或是 0.00000001 这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。
正是由于这两大局限性，才使得计数排序不像快速排序、归并排序那样被人们广泛适用。
代码示例：
void CountSort(int* a, int n) { int max = a[0], min = a[0]; for (int i = 1; i < n; i++) { //找最大 if (a[i] > max) { max = a[i]; } //找最小 if (a[i] < min) { min = a[i]; } } //算范围 int range = max - min + 1; //开计数数组 int* countA = (int*)malloc(sizeof(int) * range); if (countA == NULL) { perror("malloc fail"); return; } //初始化计数数组 memset(countA, 0, sizeof(int) * range); //计数 for (int i = 0; i < n; i++) { countA[a[i] - min]++; //通过相对位置映射计数（这是一种哈希的思想） } //排序，并覆盖原数组 int j = 0; for (int i = 0; i < range; i++) { //遍历计数数组 while (countA[i]--) { //用数据数量的有序序列对应的数据，覆盖原数组 a[j++] = i + min; //countA[i]记录了某一数据出现的次数，countA[i]出现几次，就往原数组中写几个对应的值 //i + min相当于还原出原数据 } } free(countA); }
【Tips】排序算法的复杂度&稳定性
