排序算法在很多领域得到相当重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。此文整理了一些基本的排序算法以及相关拓展。
| 排序方法 | 最差时间复杂度 | 最优时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 类别 |
|---|---|---|---|---|---|---|
| 冒泡排序 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | 稳定 | 内部比较排序 |
| 选择排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 不稳定 | 内部比较排序 |
| 插入排序 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | 稳定 | 内部比较排序 |
| 希尔排序 | \(O(n^S)\) | \(O(n)\) | \(O(n^S)\) | \(O(1)\) | 不稳定 | 内部比较排序 |
| 归并排序 | \(O(n\log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n)\) | 稳定 | 内部比较排序 |
| 快速排序 | \(O(n^2)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(\log n)\) | 不稳定 | 内部比较排序 |
| 堆排序 | \(O(n\log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | 不稳定 | 内部比较排序 |
| 桶排序 | \(O(n\log n)\) | \(O(n)\) | \(O(n + n \log n - n \log m)\) | \(O(m + n)\) | 稳定 | 非比较排序 |
| 计数排序 | \(O(n + k)\) | \(O(n)\) | \(O(n + k)\) | \(O(k)\) | 稳定 | 非比较排序 |
| 堆排序 | \(O(m(n + B))\) | \(O(n)\) | \(O(m(n + B))\) | \(O(n + B)\) | 不稳定 | 非比较排序 |
Basic Definitions
排序算法稳定性 (Sorting Algorithm Stability): 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变（即在原序列中，
r[i]==r[j]且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前），则称这种排序算法是稳定的；否则称为不稳定的。基于比较的排序算法: 若一个排序算法是基于内部比较的，则一般情况下，他的平均时间复杂度不可能优于 \(O(n\log n)\)。这就是基于内部比较的排序算法的时间复杂度下限。
Proof:
对于 n 个未知的待排序元素，可能的排序结果共有 \(A_n^n = n!\) 种；
在经过一次比较后，有两个元素之间的前后顺序被确定，在这个情况下，可能的排序结果剩下 \(\frac{n!}{2}\) 种：
假设比较了序列中的 A 和 B 这两个元素：A 与 B 在序列中的地位是平等的，在 \(n!\) 种可能的排序结果中，A 排在 B 前面的结果数与 A 排在 B 后面的结果数相等，均为 \(\frac{n!}{2}\)（注意到当 \(n > 1\) 时，\(n!\) 的因子中包含 2，因此 \(n!\) 必为偶数），经过比较后，A 与 B 之间的前后顺序确定，不妨假设 A 大于 B，则排序结果中，A 排在 B 前面的那 \(\frac{n!}{2}\) 种结果不再成立，剩下 A 排在 B 后面的那 \(\frac{n!}{2}\) 种结果；
依此类推，每经过一次比较，可能的排序结果数都会减半，直到经过 m 次比较，剩余 \(\frac{n!}{2^m}\) 种可能的排序结果；
当 \(\frac{n!}{2^m} \leq 1\) 时，可能的排序结果只剩一种，此时排序结束，计算此时的比较次数 m: \[ \frac{n!}{2^m} \leq 1 \\ 2^m \geq n! \\ m \geq \log{n!} \] （还可以这样考虑：n 个数有 \(n!\) 个可能的排列情况，也就是说基于比较的排序算法的判定树有 \(n!\) 个叶子结点；排序需要的最少比较次数可以近似地看做这棵树的深度 \(\log{n!}\)）
利用斯特林公式（Stirling's approximation）\(n ! \approx \sqrt{2 \pi n}\left(\frac{n}{e}\right)^{n}\)，有： \[ m \geq \log{n!} \approx log(\sqrt{2 \pi n}\left(\frac{n}{e}\right)^{n})=\log{\sqrt{2 \pi }} + \frac{1}{2}\log{n} + n\log{\frac{n}{e}} \] 即，最少的比较次数为： \[ O(m) = O\left(n\log{n}-n\log{e} + \frac{1}{2}\log{n} + \log{\sqrt{2 \pi }}\right)=O(n\log{n}) \]
最优时间复杂度 (Best Case Time Complexity): 最好情况下（一般为给定数组已经排序完成；最好情况视具体排序算法而定），该排序算法的时间复杂度。
最差时间复杂度 (Worst Case Time Complexity): 最坏情况下（如：给定数组的排列完全随机或给定数组已经反向排序等；最差情况视具体排序算法而定），该排序算法的时间复杂度。
平均时间复杂度 (Average Case Time Complexity): 所有可能情况下 该排序算法的时间复杂度的平均值。
注意：本文中的 \(\log n\) 默认底数为 \(2\)。
关于时间复杂度的更多信息参见：时间复杂度
Bubble Sort
冒泡排序 重复地访问过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下（以从小到大排序为例）： 1. 正向遍历，对于每一对相邻元素，比较这两个元素的大小，如果前一个比后一个大，就把它们两个调换位置。完成一次遍历后，数组的最后一个元素就是最大元素； 3. 排除最后一个元素，针对剩余数组重复上述步骤； 4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1 | // 分类 -------------- 内部比较排序 |
冒泡排序代码：
1 | def bubbleSort(alist): |
代码测试：
1 | alist = [54,26,93,17,77,31,44,55,20] |
[17, 20, 26, 31, 44, 54, 55, 77, 93]Short Bubble Sort
短冒泡排序 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到 \(O(n)\)。这种算法就是短冒泡排序。
1 | # short bubble sort: 若第一次遍历时没有进行交换，则直接停止 |
代码测试：
1 | alist=[20,30,40,90,50,60,70,80,100,110] |
[20, 30, 40, 50, 60, 70, 80, 90, 100, 110]Cocktail Sort
鸡尾酒排序 又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
以从小到大排序为例： 1. 正向遍历：对于每一对相邻元素，比较这两个元素的大小，如果前一个比后一个大，就把它们两个调换位置。完成一次遍历后，数组的最后一个元素就是最大元素； 2. 反向遍历：排除最后一个元素，针对剩余数组，从后往前遍历，对于每一对相邻元素，比较这两个元素的大小，如果前一个比后一个大，就把它们两个调换位置。完成一次反向遍历后，数组的第一个元素就是最小元素； 3. 排除第一个和最后一个元素，针对剩余数组重复上述步骤 1 和 2； 4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1 | // 分类 -------------- 内部比较排序 |
鸡尾酒排序代码：
1 | def cocktailSort(alist): |
代码测试：
1 | alist=[20,30,40,90,50,60,70,80,100,110] |
[20, 30, 40, 50, 60, 70, 80, 90, 100, 110]Selection Sort
选择排序 多次遍历数组，每次都遍历选出最大/最小元素，放到数组最后/最前的位置，直到排序完成。
选择排序算法的运作如下（以从小到大排序为例）： 1. 遍历数组，找到最大元素（通过维护一个“最大元素的位置”实现），将它放到数组最后一个位置（通过与数组最后一个元素交换位置实现）； 2. 排除最后一个元素（即最大元素），针对剩下的数组重复上述步骤； 3. 持续每次对越来越少的元素重复上面的步骤，直到完成排序。
1 | // 分类 -------------- 内部比较排序 |
选择排序代码：
1 | def selectionSort(alist): |
代码测试：
1 | alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] |
[17, 20, 26, 31, 44, 54, 55, 77, 93]Insertion Sort
插入排序 在数组中维护一个“已排序”的子序列，对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。
插入排序算法的运作如下（以从小到大排序为例）： 1. 将数组的第一个元素初始化为已排序子序列； 2. 取出下一个元素（已排序子序列的右边第一个元素）作为新元素，在已经排序的元素序列中从后向前扫描； 3. 如果已排序子序列中的某元素大于新元素，则将该元素后移一个位置，空出一个空位； 4. 重复步骤3（空位会不断左移），直到找到已排序的元素小于或者等于新元素； 5. 将新元素插入到空位中； 6. 重复步骤2 ~ 5，直到完成排序。
1 | // 分类 ------------- 内部比较排序 |
1 | def insertionSort(alist): |
代码测试：
1 | alist = [54,26,93,17,77,31,44,55,20] |
[17, 20, 26, 31, 44, 54, 55, 77, 93]Binary Insert Sort
二分插入排序 对于插入排序，如果比较操作的代价比交换操作大的话，在寻找元素插入的位置时可以采用 二分查找法 来减少插入过程中比较操作的次数。
1 | // 分类 -------------- 内部比较排序 |
当 n 较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。
1 | def binaryInsertSort(alist): |
代码测试：
1 | alist = [54,26,93,17,77,31,44,55,20] |
[17, 20, 26, 31, 44, 54, 55, 77, 93]Shell Sort
希尔排序 即分组插入排序，也叫递减增量排序(Diminishing Increment Sort)，是插入排序的一种更高效的改进版本： 1. 将数组按照一定的步长/增量（步长为 n 表示：对于任意 i, 下标为 i, i+n, i+2n, i+3n ... 的元素组成同一个子序列）拆分为若干个较小的子序列（事实上，若步长为 n， 则拆分为 n 个子序列），然后对每个子序列分别使用插入排序（这样可以让一个元素一次性地朝最终位置前进一大步-->克服了插入排序的一个导致低效的缺点：每步排序中，除了这一步的新元素外，其他元素都只能移动最多一位）； 2. 再取越来越小的步长进行分组插入排序； 3. 算法的最后一步（此时步长为1）就是普通的插入排序，但是到了这步，数组已经几乎排列好了，因此这步的排序效率也比较高（利用了插入排序在对几乎已经排好序的数据操作时效率较高的优点）。
注意：一般取 \(\frac{n}{2}\) 作为第一个步长，此后依次用 \(\frac{n}{4}\), \(\frac{n}{8}\), ... 直到最后一个步长为 1.
1 | // 分类 -------------- 内部比较排序 |
1 | def shellSort(alist): |
代码测试：
1 | alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] |
After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]
After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]
After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]
Finally: [17, 20, 26, 31, 44, 54, 55, 77, 93]Merge Sort
归并排序 采用分治法（以从小到大排序为例）： * 分割：把当前序列平均分割成前后两个子序列，对每个子序列递归地执行该分割操作 -> 最终得到许多长度为1的子序列； * 集成/归并：对于两个子序列，将他们的所有元素按照大小顺序排列在一起，集成为一个排好序的序列 -> 最终归并得到完整的排好序的序列。一个归并单元的步骤如下： 1. 申请空间，使其大小为两个已经排序的子序列之和，该空间用来存放合并后的序列，称为合并空间/临时数组； 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置； 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间/临时数组，并将指向较小元素的指针移动到下一位置； 4. 重复步骤3直到某一指针到达序列尾部； 5. 将另一序列剩下的所有元素直接复制到合并空间/临时数组尾部；
1 | // 分类 -------------- 内部比较排序 |
关于时间复杂度：
- 假设长度为 \(n\) 的数组的归并排序整体的时间复杂度为 \(T(n)\)，其中包括递归步骤中 2 个长为 \(n/2\) 的子序列的归并排序消耗的时间复杂度 \(T(n/2)\)，以及最后把这两个有序子序列合并成一个数组的时间复杂度 \(O(n)\)。因此有 \(T(n) = 2\times T(n/2) + O(n)\)；
- 类似的，如果考虑长度为 \(n/2\) 的数组，我们有 \(T(n/2) = 2 \times T(n/4) + O(n/2)\)；
- 将 2 中的式子代入 1 中，可以得到：\(T(n) = 2 \times 2 \times T(n/4) + 2 \times O(n)\)；
- 考虑长度为 \(n/4\) 的数组，再经过一次上述代入可以得到：\(T(n) = 2^3 \times T(n/8) + 3 \times O(n)\)；
- 可以得出结论，对于 \(m = 1,2,3,...\)，有递推式：\(T(n) = 2^m \times T(\frac{n}{2^m}) + m \times O(n)\)；
- 当 \(m\) 取值达到 \(logn\) 时，有 \(\frac{n}{2^m}=1\)，表示 \(m\) 的取值已达上限，此时有：\(T(n) = 2^{logn} \times T(1) + (logn) \times O(n) = n \times T(1) + O(nlogn)\)；
- 由于 \(T(1)\) 为常量，在计算时间复杂度时可忽略，且因此有：\(T(n) = O(nlogn)\)。
关于空间复杂度：额外需要的空间就是那个合并空间/临时数组占用的空间 \(O(n)\) 和递归时（显然需要 \(logn\) 次递归）压入栈的数据占用的空间 \(O(logn)\)，故整体的空间复杂度为 \(O(n)\)。
1 | def mergeSort(alist): |
代码测试：
1 | alist = [54,26,93,17,77,31,44,55,20] |
Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting [54, 26, 93, 17]
Splitting [54, 26]
Splitting [54]
Merging [54]
Splitting [26]
Merging [26]
Merging [26, 54]
Splitting [93, 17]
Splitting [93]
Merging [93]
Splitting [17]
Merging [17]
Merging [17, 93]
Merging [17, 26, 54, 93]
Splitting [77, 31, 44, 55, 20]
Splitting [77, 31]
Splitting [77]
Merging [77]
Splitting [31]
Merging [31]
Merging [31, 77]
Splitting [44, 55, 20]
Splitting [44]
Merging [44]
Splitting [55, 20]
Splitting [55]
Merging [55]
Splitting [20]
Merging [20]
Merging [20, 55]
Merging [20, 44, 55]
Merging [20, 31, 44, 55, 77]
Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]另外一种写法：
1 | # another method |
代码测试：
1 | alist = [54,26,93,17,77,31,44,55,20] |
[17, 20, 26, 31, 44, 54, 55, 77, 93]Quick Sort
快速排序 是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 \(n\) 个元素要 \(O(n\log{n})\) 次比较。在最坏状况下则需要 \(O(n^2)\) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 \(O(n\log{n})\) 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序算法的运作如下（以从小到大排序为例）： 1. 从序列中挑出一个元素（通常选择第一个元素或者中间位置的元素），作为"基准" (pivot)； 2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（与基准相同的数可以到任一边），这个过程称为分区 (partition) 操作； 3. 对每个分区序列递归地进行步骤 1~2，递归的结束条件是分区序列的长度为 0 或 1，这时序列整体已经排序完成。
1 | // 分类 ------------ 内部比较排序 |
注意：若每次选取的基准都恰好是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行 \(n-1\) 次划分才能结束递归，则快速排序算法就退化成了冒泡排序。
1 | def partition(alist, first, last): |
代码测试：
1 | alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] |
[31, 26, 20, 17, 44, 54, 77, 55, 93]
[17, 26, 20, 31, 44, 54, 77, 55, 93]
[17, 26, 20, 31, 44, 54, 77, 55, 93]
[17, 20, 26, 31, 44, 54, 77, 55, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
Finally [17, 20, 26, 31, 44, 54, 55, 77, 93]另外一种写法，更简洁，但是使用了额外空间：
1 | # another method: 更简洁，但是使用了额外空间 |
代码测试：
1 | alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] |
[17, 20, 26, 31, 44, 54, 55, 77, 93]注意：Java 系统提供的 Arrays.sort 函数，对于基础类型，底层使用快速排序；对于非基础类型，底层使用归并排序。请问是为什么？
答：这是考虑到排序算法的稳定性。对于基础类型，相同值是无差别的，排序前后相同值的相对位置并不重要，所以选择更为高效的快速排序，尽管它并不稳定；而对于非基础类型，排序前后相等实例的相对位置不宜改变，所以选择稳定的归并排序。
Linked List Quick Sort
链表快速排序 使用快速排序对链表进行排序。此处使用两个指针进行分区操作：（该操作的核心为：确保 i 以及 i 之前的元素都小于基准数，i 之后的元素都大于基准数；j 用于遍历一次整个链表，指向当前处理的那个元素）
- step1: 初始化时，
i指向链表首元素；j = i + 1，指向链表第二个元素。基准数字为当前i指向的数字（即首元素）；
- step2: 若
j指向的元素大于基准数：直接跳过，执行j++；
- step3: 若
j指向的元素小于基准数：首先i向后移动一位（i++），然后交换i和j所指向的元素（swap(i,j)），最后j向后移动一位（j++）；
- step4: 最后，当
j已经超出索引，则一次循环结束，交换当前i指向的元素和基准数；
- step5: 以基准数当前所在的位置为界划分了左右两个子链表，递归地对这两个子链表进行上述快速排序的操作即可
1 | # 方法2 |
4 2 5 3 7 9 0 1
4 2 3 5 7 9 0 1
4 2 3 0 7 9 5 1
4 2 3 0 1 9 5 7
1 0 3 2 4 9 5 7
0 1 3 2 4 9 5 7
0 1 2 3 4 9 5 7
0 1 2 3 4 9 5 7
0 1 2 3 4 7 5 9
0 1 2 3 4 5 7 9 Heap Sort
堆排序 利用了堆这种数据结构。二叉堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者总是大于）它的父节点。
通常堆是通过一维数组来实现的。在数组起始位置为 0 的情形中： * 父节点 i 的左子节点在位置 (2i+1); * 父节点 i 的右子节点在位置 (2i+2); * 子节点 i 的父节点在位置 floor((i-1)/2);
堆排序算法的运作如下（以从小到大排序为例）： 1. 由输入的无序数组构造一个最大堆（父结点的值总是大于它的孩子节点），作为初始的无序区； 2. 把堆顶元素（最大值）和堆尾元素（堆按层次遍历的最后一个元素，即实现堆的数组的最后一个元素）互换，这时候数组最后一个元素就已经是最大元素了； 3. 排除堆尾元素，对剩下的堆重新维持一个最大堆的结构； 4. 持续每次对越来越少的元素重复步骤2 ~ 3，直到当前堆的大小为 1，此时按照层次遍历的顺序输出堆即是排序后的数组。
1 | // 分类 -------------- 内部比较排序 |
堆排序具体有如下两个关键步骤：
I. 初始化最大堆
初始化建堆过程首先会将输入的无序数组看作一个二叉树（使无序数组先满足二叉树的结构性质），然后只需要由下至上、由右至左（即：对数组逆序地进行遍历）地对所有非叶子节点（即有孩子的节点）调用 sift_down() 函数（构建最大堆时，该函数会将当前节点与它的左右子节点中较大的那一个交换，使得该节点一直下沉，直到它比左右子节点都大为止）将他们调整到合适的位置即可。 * 为什么不需要操作叶子节点：倒数第二层的节点调整位置时已经考虑到了跟最后一层节点之间的大小关系； * 为什么要逆序地遍历节点：因为建堆是一个节点下沉的过程，当一个节点向下沉的时候，必须确保它的左子树和右子树都已经满足了最大堆/最小堆的性质，这样才能确保当前节点下沉时换上来的那个值一定是当前节点的所有孩子节点中最大/最小的那一个，从而保证整体的最大堆/最小堆性质不被打破；
假设该二叉树一共有 \(k\) 层（根节点算第一层），则除了第 \(k\) 层（这一层不一定满节点）外，第 \(i\) 层的节点数为 \(2^{(i-1)}\)。建堆过程中:
倒数第二层（即第 \(k-1\) 层）的节点共有 \(2^{(k-2)}\) 个，每个节点在最坏情况下（即：该节点需要沉到最后一层）进行下沉时需要交换 1 次；
倒数第三层（即第 \(k-2\) 层）的节点共有 \(2^{(k-3)}\) 个，每个节点在最坏情况下（即：该节点需要沉到最后一层）进行下沉时最多需要交换 2 次；
... 根节点（即第 1 层）在最坏情况下（即：该节点需要沉到最后一层）进行下沉时最多需要交换 \((k-1)\) 次；
总结可以得到：第 \(i\) 层的节点共有 \(2^{(i-1)}\) 个，每个节点在最坏情况下（即：该节点需要沉到最后一层）进行下沉时最多需要交换 \(k-i\) 次，则该层总共需要的交换次数为 \(2^{(i-1)} \times (k-i)\) 次。其中 \(i=(k-1),(k-2),...,1\)。
因此，在最坏情况下，完成建堆过程总共需要进行 \(\sum_{i=k-1}^{1}[2^{(i-1)} \times (k-i)]\) 次交换。注意到，节点数量为 \(n\) 的完全二叉树的高度 \(k\) 大致为 \(\log n\)，因此代入 \(k = \log n\)，建堆过程需要的时间复杂度为 \(T(n) = \sum_{i=\log n-1}^{1}[2^{(i-1)} \times (\log n-i)]\)。下面是 \(T(n)\) 的求解过程： \[T(n) = \frac{2^{\log n}}{4}\times1 + \frac{2^{\log n}}{8}\times2 + \frac{2^{\log n}}{16}\times3 + ... + \frac{2^{\log n}}{2^{\log n}}\times(\log n-1)\\ = \frac{n}{4}\times1 + \frac{n}{8}\times2 + \frac{n}{16}\times3 + ... + \frac{n}{2^{\log n}}(\log n-1)\]
\[2T(n) = \frac{n}{2}\times1 + \frac{n}{4}\times2 + \frac{n}{8}\times3 + ... + \frac{n}{2^{\log n-1}}(\log n-1)\]
\[2T(n) - T(n) = \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + ... + \frac{n}{2^{\log n-1}} - \frac{n}{2^{\log n}}\times (\log n-1) \\ = n\times\bigg[\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... + \frac{1}{2^{\log n-1}}\bigg] - \bigg[\frac{n}{2^{\log n}}\times (\log n-1)\bigg] \\ = n\times\bigg[\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... + \frac{1}{2^{\log n-1}}\bigg] - \bigg(\log n-1\bigg) \\ \leq n - (\log n - 1) \leq n\]
即：\(T(n) \leq O(n)\)，因此建堆过程的最差时间复杂度为 \(O(n)\)。
II. 排序重建堆
交换堆顶元素和堆尾部元素后，需要对堆进行重建以维持最大堆结构：只需要对交换后新的堆顶元素调用 sift_down() 函数下沉到合适的位置即可。而对于高度为 \(k\) 的堆，堆顶元素下沉时最坏情况下（即：该元素被下沉到堆的最后一层），最多需要交换 \(k\) 次。注意到，节点数量为 \(n\) 的完全二叉树的高度 \(k\) 大致为 \(\log n\)，因此代入 \(k=\log n\)。
需注意每次重建意味着有一个节点出堆（交换后，新的堆尾元素被排除出堆），所以每经过一次重建，都需要将堆的容量减 1（容量从 \(n\) 减少到 1）。排序过程一共需要重建最大堆 \(n-1\) 次，总的比较/交换次数为：\(\log n + \log(n-1) + ... + \log3 + \log2 = \log(n!)\)。
可以证明 \(\log(n!)\) 和 \(n\log(n)\) 是同阶无穷大：
\[\because \big(\frac{n}{2}\big)^{\frac{n}{2}} \leq n! \leq n^n\]
\[\therefore \big(\frac{n}{4}\big)\log n = \big(\frac{n}{2}\big)\log (n^{\frac{1}{2}}) \leq \big(\frac{n}{2}\big)\log (\frac{n}{2}) \leq \log(n!) \leq log(n^n) = n \log n\]
显然 \((\frac{n}{4})\log{n}\) 与 \(n\log{n}\) 同阶，根据夹逼理论，可证 \(\log(n!)\) 和 \(n\log(n)\) 同阶。
因此所有重建过程的时间复杂度总合为 \(O(n\log n)\)。
完整的时间复杂度
完整的时间复杂度为上述两者中较为高阶的 \(O(n\log n)\)。
1 | def heapSort(alist): |
代码测试：
1 | alist = [9, 2, 1, 7, 6, 8, 5, 3, 4] |
[1, 2, 3, 4, 5, 6, 7, 8, 9]Bucket Sort
桶排序 将数组中的元素按照一定的规则（如：使用某种映射函数将元素映射到桶中等；一般情况下会按照数值区间来进行分配）分配到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。 * 由于桶排序本身不是基于比较算法的排序（不考虑每个桶内使用的排序算法），因此不受基于比较的排序算法时间复杂度下限 O(nlogn) 的影响，甚至可以达到 O(n) 的时间复杂度。 * 如果数组的数据是均匀分布在某一个区间上，则桶排序的效果较好。
1 | // 分类 -------------- 不基于比较的排序（不考虑每个桶内部使用的排序算法） |
关于时间复杂度： * 若原数组有 n 个元素，算法使用了 m 个桶，则平均时间复杂度的计算如下： 1. 将每个元素分配/映射到对应的桶中：这一步一共进行了 n 次，因此时间复杂度为 \(O(n)\)； 2. 每个桶内部进行排序：若映射函数能将元素比较平均地分配到每一个桶中，则每个桶中都有 \(\frac{n}{m}\) 个元素；假设桶内部使用最快的比较排序算法（达到基于比较排序算法的时间复杂度下限），则每个桶内部排序的时间复杂度为 \(O(\frac{n}{m} \times log(\frac{n}{m}))\)；一共有 m 个桶，因此这一步的时间复杂度为 \(O(m \times \frac{n}{m} \times log(\frac{n}{m}))\)； * 则总的时间复杂度为：\(O(n) + O(m \times \frac{n}{m} \times log(\frac{n}{m})) = O(n + nlogn - nlogm)\)，这表明当 n 不变时，桶的个数 m 越大（越接近 n ），总的时间复杂度就趋向于越小。 * 如果桶的个数 m 等于原数组元素个数 n，则上述时间复杂度就达到了线性的 \(O(n)\)。
关于空间复杂度： 桶排序中，需要创建 m 个额外空间用于记录每个桶，以及 n 个额外空间用于将所有元素放入桶中，因此总的空间复杂度为 \(O(n + m)\)。
Example 1
整型桶排序（m=n）
当每个元素都是整型时，如果将桶的个数 m 设定为等于原数组的元素个数 n，即每个桶能够对应一个特定元素，则可以省去桶内部排序的过程，达到时间复杂度 O(n)；同时由于 m == n，可以得到空间复杂度也为 O(n)。对于整数数组 A 的桶排序具体步骤如下：
- 计算得到数组
A的最大值max和最小值min； - 申请一个数组
S，里面含有(max-min+1)个桶，每个桶的值初始化为 0（数组S的每一个位置代表一个桶）； - 然后遍历数组
A，遍历到A[i]时，将S[A[i]-min]的值增加 1。当遍历结束后，S 记录了每个数字出现的次数； - 所有输入被读进后，扫描数组
S，对于S的下标为i的位置，输出s[i]个(i+min)，就能得出排好序的结果。
举个例子，若要排序一个数组
[5,3,6,1,2,7,5,10]，由于值都在 1-10 之间，因此建立 10 个桶：
[0 0 0 0 0 0 0 0 0 0]（桶）
[1 2 3 4 5 6 7 8 9 10]（桶对应的数值）遍历数组，第一个数字为 5，因此第五个桶的值加 1：
[0 0 0 0 1 0 0 0 0 0]第二个数字为 3，因此第三个桶的值加 1：
[0 0 1 0 1 0 0 0 0 0]...
遍历后
[1 1 1 0 2 1 1 0 0 1]（桶的值）输出
[1 2 3 5 5 6 7 10]
1 | def bucketSort(A): |
代码测试：
1 | A = [5,3,6,1,2,7,5,10,-3,15] |
[-3, 1, 2, 3, 5, 5, 6, 7, 10, 15]Example 2
区间 [0,1) 上均匀分布的桶排序 (m=n)
当输入符合均匀分布时，例如，元素均匀的分布在区间 [0,1) 上，可以将桶排序与其它排序方法结合使用。
如果序列的长度为 n，就将 [0,1) 划分成 n 个相同大小的子区间（桶 s），然后将 n 个输入数放入它们所属数值区间对应的各个桶中（例如：假如输入 10 个数，则把区间 [0,1) 均匀划分为 10 个区间，而 0.09 落在区间 [0, 0.1)，所以 0.09 分配到桶 s[0]）。对各个桶中的数进行内部排序，然后按照次序把各桶中的元素列出来即可。
1 | def bucketSort(A): |
代码测试：
1 | A = [0.09,0.27,0.81,0.03,0.48] |
[0.03, 0.09, 0.27, 0.48, 0.81]Example 3
一般情况下的桶排序（m<=n）
在一般情况下，对于数组 A 的桶排序具体步骤如下： 1. 计算得到数组 A 的最大值 max 和最小值 min以及数组长度 n； 2. 设定一个小于 n 的整数 m 作为桶的个数； 3. 申请一个数组 S，里面含有 m 个桶，每个桶的值初始化为 0（数组 S 的每一个位置代表一个桶）； 4. 将区间 [min, max] 分为 m 等分，得到 m 个 [·,·) 型子区间（注意：最后一个子区间需要是 [·,·]型，用于将 max 包括进去），每个子区间对应一个桶； 5. 把数组 A 的每个元素按照所在子区间分配到对应的一个桶中，具体步骤如下： * 由于 [min, max] 被分为了 m 等分，因此每个子区间的长度为：\(width = \frac{max - min}{m}\)； * 显然元素 x 落在第 i 个区间，其中 \(i = int(\frac{x - min}{width}) = int(\frac{(x - min)m}{max - min})\)； * 因此，将元素 x 分配到第 i 个桶，即 S[i] 对应的桶； * 注意：数组中最大的元素 max 需要将直接放到最后一个桶中； 6. 每个桶进行内部排序（使用某种排序算法）； 7. 按顺序将每个桶内排好序的序列输出，就得到了整体排序完成的序列。
1 | def bucketSort(A, m): |
代码测试：
1 | A = [0.09,81,1000,-23,0,0.78,9.2] |
[-23, 0, 0.09, 0.78, 9.2, 81, 1000]Counting Sort
计数排序 基本思想是对于给定的输入序列中的每一个元素 x ，确定该序列中值小于等于 x 的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将 x 直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有 17 个元素的值小于等于 x 的值，则 x 可以直接存放在输出序列的第 18 个位置上。
类型一：适用于非负整数 对每一个输入的元素 A[i]，通过辅助数组 c（而不是通过比较大小）确定 A 中小于等于 A[i] 的元素个数，具体方法为：
- 计算得到
k = max(A)，以此确定输入数组的范围为0 ~ k（因为是非负整数），然后申请一个长为(k+1)的数组c（其下标为0 ~ k，原始数组中的每个数都能对应一个下标）；
- 遍历原数组
A，用c[x]储存A中数字x出现的次数；
- 遍历辅助数组
c，将c[x]更新为A中小于等于x的数字出现的总次数；
- 申请输出数组
output，然后逆序遍历原始数组A，对于A的每一个元素，基于辅助数组c的信息将该元素放入它排序后应该在的位置（例如：遍历到A中的一个元素 x，如果c[x] == 17，则表明原数组中共有 17 个元素小于等于x，因此将该元素x放在output[16]的位置）； - 注意：每将一个元素
x放入output对应的位置后，需要同步地将相应的c[x]的值减去 1。这是因为，如果在继续遍历A的过程中，又遇到了重复的元素x，则这个新的x在放入output中时，需要放在上一个放入的x的前面（不能抢占上一个x的位置；而由于“小于等于”的条件，它也不能放到上一个x的后面）。 - 注意：在步骤 4 中，之所以要逆序遍历原始数组
A，是因为在遍历遇到重复元素x时，之后遇到的那个x会被放在上一个遇到的x的前面，因此，如果不逆序遍历A的话，就无法保证算法的稳定性。
1 | // 分类 -------------- 不基于比较的排序 |
关于时间复杂度：步骤 2 中遍历 A 需要时间为 O(n)；步骤 3 中遍历 c 需要时间为 O(k)；步骤 4 中逆序遍历 A 需要时间为 O(n)；三者相加得到整体的时间复杂度为 O(n + k)。
1 | def countingSort(A): |
代码测试：
1 | A = [17,4,5,3,7,9,15] |
[3, 4, 5, 7, 9, 15, 17]优化：突破非负整数的限制 之所以会有非负整数的限制，是因为列表 c 的下标自然地从 0 开始标，导致他能标记的元素值被限定在 0~k 的范围内。因此如果考虑使用一个字典 d[x] 代替列表 c[x] 来储存 A 中小于等于元素 x = A[i] 的元素个数，用键值取代下标，就能实现从 min(A) ~ max(A) 的标号，从而突破这一限制，将负数也纳入考虑范围。（也可以考虑通过滑动调整下标突破这一限制：让 c[x - min(A)] 储存 A 中小于等于元素 x = A[i] 的元素个数即可）。
1 | // 分类 -------------- 不基于比较的排序 |
关于时间复杂度：步骤 2 中遍历 A 需要时间为 O(n)；步骤 3 中遍历 c 需要时间为 O(max(A) - min(A))；步骤 4 中逆序遍历 A 需要时间为 O(n)；三者相加得到整体的时间复杂度为 O(n + max(A) - min(A))。
下面的代码使用字典来进行优化：
1 | def countingSort(A): |
代码测试：
1 | A = [17,4,5,3,7,9,15,-9,-12] |
[-12, -9, 3, 4, 5, 7, 9, 15, 17]类型二：基于比较的计数排序
这个类型的计数排序无法突破基于比较的排序算法的时间复杂度下界 O(nlogn)，但是可以用于包含负数的数据。具体思路如下：
对输入数组中的每一个数 A[i]，通过比较确定出小于 A[i] 的数字的总个数 p 和等于 A[i] 的数字的总个数 q。有了这一信息就可以把 A[i] 直接放到排序后数组中的相应位置（排序后数组的下标为 p 到 (p + q) 的位置上都应该放置 A[i]）。
1 | def countingSort(A): |
代码测试：
1 | A = [9,8,5,6,3,3,2,2,-9] |
[-9, 2, 2, 3, 3, 5, 6, 8, 9]Radix Sort
基数排序 当数组中的元素都是非负整数时候，可以考虑使用基数排序。基数排序的基本思想就是：把元素从个位排好序，然后再从十位排好序，重复直到元素中最大数的最高位排好序，那么整个元素就排好序了。
假设使用十进制数字（即基数 B=10），且输入列表 A 中最大数字的最高位数是 m 位，则基数排序的算法过程如下： 1. 根据设定的基数 B 划分出 B 个桶：例如，按照十进制（基数 B=10），则分为 0 ~ 9 这十个桶； 2. 遍历位数，从个位、十位、... 到第 m 位进行 m 次分桶（从低位向高位进行），具体分桶操作如下： * 分配：遍历原数组，将数字按照当前位数分配到对应的桶中。例如，数字为 327，当前是按照十位数分桶，则 327 会被分到 2 号桶；若是数字 10，当前按照个位数分桶，则 10 会被分到 0 号桶； * 收集：每次分桶完毕后，按桶的顺序排列依次输出桶内数字，得到一个新的序列； * 下一轮（即基于下一个位数）的分桶将针对上述新序列进行； 3. 所有分桶结束后（即最高位 m 位也完成分桶），按桶的顺序排列依次输出桶内数字就能得到排序完成的序列。
1 | // 分类 -------------- 不基于比较的排序 |
关于时间复杂度：
基数排序一共进行了 m 次分桶操作，而每次分桶操作中包含以下两个部分： 1. 分配步骤：把原数组的每个元素都分配到一个对应的桶中。由于 n 个元素每个都被分配了一次，因此这一步的时间复杂度为 O(n)； 2. 收集步骤：把每个桶中的所有元素依次输出到一个新的序列中。由于 B 个桶每个都被收集了一次（每个桶内所有元素以一个数组为单位被输出，因此只有一次操作），因此这一步的时间复杂度为 O(B)；
因此，m 次分桶操作的总体时间复杂度为 O(m * (n + B))，这也就是基数排序的平均时间复杂度。
关于空间复杂度：
需要创建 B 个额外空间用于记录每个桶，以及 n 个额外空间用于将所有元素放入桶中，因此总的空间复杂度为 O(n + B)。
注意：
- 基数排序适用于非负整数；
- 数组元素的最大值和最小值差距如果比较小，则比较适用基数排序；
- 基数排序可以看做是特殊的桶排序：普通的桶排序是按值区间划分桶，而基数排序是按数位来划分；基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序；
- 如果使用数组元素的最大值作为基数，基数排序就退化成了计数排序；
- 对于某个数组，如果使用二进制（取 B = 2）进行基数排序，则相比其他基数选值，B 达到了可能的最小值 2，相应地，这个进制下，数组元素的最高位数 m 就达到了最大值，时间复杂度 O(m * (n + B)) 会变大，空间复杂度 O(n + B) 会变小；
- 对于某个数组，如果使用其元素的最大值作为基数进行基数排序， 则相比其他基数选值，B 达到了可能的最大值，相应地，这个进制下，最高位数 m 仅为 1，时间复杂度 O(m * (n + B)) 会变小，空间复杂度 O(n + B) 会急剧增大，此时基数排序退化成了计数排序。
1 | def radixSort(A): |
代码测试：
1 | A = [99, 108, 425, 0, 10, 809, 32, 78, 933, 26, 3397] |
[0, 10, 26, 32, 78, 99, 108, 425, 809, 933, 3397]