实现代码传送门
1. 基本概念
1.1. 稳定性
对于任一无序序列，如果每次排序的结果各个元素对应的下标都是不变的，则该排序是稳定的。
1.2. 内/外部排序
待排序序列在内存中的为内部排序，反之为外部排序。
下面以输入无序数组为 \(A=[a_0, a_1, ..., a_n]\) ，基于原序列且升序的内部排序为例
2. 插入排序（straight insert sort）
2.1. 基本思想
插入排序是最简单的排序方法。
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
2.2. 实现过程
- 从前往后遍历无序表，设当前遍历元素的下标为 \(i\)，则 \([0, i)\) 的区间为有序列表（可以从后面的步骤中证明这一结论）。
- 缓存 \(a_i\) ，然后从后往前遍历 \([0, i)\) 区间，当出现第一个下标为 \(j\) 的元素比 \(a_i\) 小时（如果找不到有比 \(a_i\) 小的元素，则 \(j=0\)），将 \([j, i)\) 区间集体往后挪一位，然后将 \(a_i\) 插入到下标为 \(j\) 的位置上。
- 循环步骤1~2，直到无序表遍历完毕。
2.3. 实现样例
3. 希尔排序（shell sort）
3.1. 基本思想
插入排序算法的改进版本——从减少序列长度和序列基本有序两个方面进行改进。
首先按照一个较大的增量取值分组，再对每个分组分别进行插入排序。然后合并各分组，再选择更小的增量取值分组排序，使这个序列趋向于基本有序。
3.2. 实现过程
- 设置一个初始增量 \(d_0\)，则输入序列会被分成 \(d_0\) 个分组。例如，设 \(d_0=5\)，则 \([d_0, d_5, d_{10}, ...,d_{5i}]\) 为一个分组序列。对每个分组序列各个组内进行直接插入排序。
- 逐渐减少 \(d_0\) （直到 \(d_0=1\) ），重复步骤1。
3.3. 实现样例
4. 冒泡排序（bubble sort）
4.1. 基本思想
相邻元素比较交换，轻者上浮，重者下沉。
4.2. 实现过程
- 从后往前遍历无序表，设当前遍历元素的下标为 \(i\)
- 从前往后遍历 \([0, i)\) 区间，设当前遍历元素的下标为 \(j\)，如果 \(a_j>a_{j+1}\) ，则交换 \(a_j\) 和 \(a_{j+1}\) 的值。
- 循环步骤1~2，直到 \(i=0\)
4.3. 实现样例
5. 快速排序（quick sort）
5.1. 基本思想
又叫划分排序，最快的排序，是气泡排序改进版。快速排序比较和交换从两端向中间进行，每次选取一个基点，将小于基点的元素换到前面，大于基点的元素换到后面。通过对两个不相邻的元素的一次交换，间接地消除多个逆序。
然后以基点为界把原序列分成两个子序列，分别对子序列递归上述操作，即可得到一个有序序列。
其本质上是二叉搜索树的思想。
5.2. 实现过程
- 设输入一个搜索子区间 \((l, r]\)（初始化时，\(l=0,r=n-1\)），设立当前基点为 \(a_{l}\)
- 从前往后遍历子区间，寻找第一个比基点大的元素的下标 \(i\)
- 从后往前遍历子区间，寻找第一个比基点小的元素的下标 \(j\)
- 如果 \(i<j\)，则交换这两个下标的元素
- 子区间变为 \((i, j)\)，重复步骤2~4，直到 \(i > j\)
- 如果 \(l \neq j\)，则交换 \(a_l\) 和 \(a_j\)
- 把子区间分为 \((l, j-1]\) 和 \((j+1, r]\) 两部分，分别递归重复步骤1~6，直到区间不能再被划分。
5.3. 实现样例
6. 选择排序（straight select sort）
6.1. 基本思想
每次从无序列表中抽取一个最小值，并将其拼接到有序表后面。
6.2. 实现过程
- 从前往后遍历无序表，设当前遍历元素的下标为 \(i\)，则 \([0, i)\) 的区间为有序列表（可以从后面的步骤中得出这一结论）。
- 从 \((i, n)\) 区间中寻找最小值，设其下标为 \(j\)，如果 \(a_i > a_j\)，则交换这两个元素
- 重复步骤1~2，直到无序表表里结束
6.3. 实现样例
7. 堆排序（heap sort）
7.1. 基本思想
对选择排序的改进。把序列构成一个大根堆（理论上应该是做小根堆，但大根堆有利于不使用辅助数组的情况），每次取根节点，插入到有序表的第一位中，然后对堆进行重构。不断重复对堆取点重构操作，直到堆为空。
关于堆的相关操作，可以看我之前写的这篇博客
7.2. 实现过程
- 按堆的构造流程，对输入序列调整为顺序表存储形式的大根堆。
- 把堆头元素与堆尾元素交换。设堆尾元素为 \(i\)，交换后，区间 \([0, i)\) 为堆，通过筛运算，对其重新重构为一个大根堆
- 重复步骤2，直到堆为空。
7.3. 实现样例
8. 归并排序（merge sort）
8.1. 基本思想
从两个单位长度的序列开始，不断把两个小的有序表合并成一个大的有序表（2路归并），最终得到一个总体的有序表。
该算法可以使用递归实现，也可以使用循环实现。下面讲解的是循环的实现流程。
8.2. 实现过程
- 初始化一个步长 \(d=1\)
- 从前往后遍历输入序列，每次取长度为 \(2d\) 的区间，作为本次需要合并的区间。设当前下标为 \(i\)，则 \([i, i + d)\) 和 \([i+d, i+2d)\) 为左右两个待合并的小的有序表，如果右区间为空（判定下标是否越界），则跳到步骤4
- 创建一个辅助数组，然后对两个待合并的小的有序表，进行如下合并操作：每次比较两个区间中的第一个元素，将较小的元素取出并拼接到辅助数组后面，重复该操作，直到其中一个区间为空，然后把另一个区间拼接到辅助数组后面。最后用辅助数组替换区间 \([i, i+2d)\)
- 将步长增大一倍，重复步骤2~3，直到步长不小于一个输入序列长度。
8.3. 实现样例
9. 基数排序（radix sort）
9.1. 基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
下面以基于十进制为例说明过程
9.2. 实现过程
- 设立一个记录进制数的变量 \(r=10\)，判断输入序列中最大值的位数 \(k\) ，设最大值为 \(m\)，则计算公式为 $k = _{r} m $
- 创建 \(r\) 个桶（bucket），并按顺序进行编号。从低位开始遍历。设当前遍历到第 \(i\) 位，然后从前往后遍历输入数组，提取当前元素第 \(i\) 位的值，然后按其提取值放进对应的桶中。
- 输入数组遍历完毕后，按顺序复制到原数组中，形成一个新的数组。
- 重复步骤2~3，直到每一位都遍历完毕。
10. 附：各种排序算法的复杂度
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏) | 时间复杂度（最好) | 空间复杂度 | 稳定性 | 复杂性 | 最佳应用情况 |
|---|---|---|---|---|---|---|---|
| 直接插入排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | 稳定 | 简单 | 输入序列长度短，且基本有序 |
| 希尔排序 | \(O(n \log n)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | 不稳定 | 较复杂 | 输入序列为顺序表结构，长度长，且基本无序 |
| 冒泡排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | 稳定 | 简单 | 输入序列长度短，且基本有序 |
| 快速排序 | \(O(n \log n)\) | \(O(n^2)\) | \(O(n \log n)\) | \(O(n \log n)\) | 不稳定 | 较复杂 | 输入序列为顺序表结构，长度长，且基本无序 |
| 直接选择排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(O(1)\) | 不稳定 | 简单 | 输入序列基本正序 |
| 堆排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | 不稳定 | 较复杂 | 输入序列长度长 |
| 归并排序 | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n)\) | 稳定 | 较复杂 | 任意输入序列 |
| 基数排序 | \(O(d(n+rd))\) | \(O(d(n+rd))\) | \(O(d(n+rd))\) | \(O(n+rd)\) | 稳定 | 较复杂 | 需要知道输入序列的取值范围且取值范围相差不大 |
Farewell~
