第八章排序
8.1 排序的基本概念
排序（Sort），就是重新排列表中的元素，使表中的元素满⾜按关键字有序的过程。
算法的稳定性。若待排序表中有两个元素 Ri 和 Rj，其对应的关键字相同即 keyi = keyj，且在排序前 Ri 在 Rj 的前⾯，若使⽤某⼀排序算法排序后，Ri 仍然在 Rj 的前⾯，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
8.2 插入排序
8.2.1 直接插入排序
算法思想：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成
空间复杂度：O (1)
最好时间复杂度—— O (n)
最坏时间复杂度——O (n 2)
平均时间复杂度：O (n 2)
8.2.2 折半插入排序
先⽤折半查找找到应该插⼊的位置，再移动元素
当 low>high 时折半查找停⽌，应将 [low, i-1] 内的元素全部右移，并将 A[0] 复制到 low 所指位置
当 A[mid]==A[0] 时，为了保证算法的 “稳定性”，应继续在 mid 所指位置右边寻找插⼊位置
仅减少了比较元素的次数, 移动的次数并未改变
8.2.3 希尔排序
** 希尔排序：** 先将待排序表分割成若⼲形如 L[i, i + d, i + 2 d,…, i + kd] 的 “特殊” ⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量 d，重复上述过程，直到 d=1 为⽌。
空间复杂度：O (1)
时间复杂度：和增量序列 d 1, d 2, d 3… 的选择有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度
稳定性：不稳定
适⽤性：仅适⽤于顺序表，不适⽤于链表
8.3 交换排序
8.3.1 冒泡排序
** 冒泡排序：** 从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即 A[i-1]>A[i]），则交换它们，直到序列⽐较完。
实现步骤：
- 从最后一个元素开始, 两两相邻进行比较, 若为逆序, 则交换它们
- 一趟冒泡, 结果将最小的元素交换到第一个位置
- 下一趟冒泡, 前一趟确定的最小元素不再参与, 待排序列减少一个元素
- 每趟冒泡的结果是序列中最小元素放到最终位置, 最多 n-1 此完成
8.3.2 快速排序
更⼩的元素都交换到左边更⼤的元素都交换到右边
实现步骤：
- 每次取当前表中第一个元素作为基准 pivot (枢轴值) 对表进行划分
- I 指向第一个元素 (基准), j 指向最后一个元素
- 先从 j 开始, 从后往前找到第一个比基准小的元素, j 指向此元素位置, 用此元素替换掉 i 所指元素
- 再从 i 开始, 从前往后找到第一个比基准大的元素, i 指向此元素位置, 用此元素替换掉 j 所指元素
- 再次从 j 开始, 循环往复, 直到 i 与 j 接触停止, 将基准值放到接触位置, 将序列划分为两块, 前面小于基准值, 后面大于基准值
- 分别取两个子序列的第一个元素作为基准值, 重复操作
时间复杂度 = O (n * 递归层数)
最好时间复杂度 = O (nlog 2 n)
最坏时间复杂度 = O (n 2)
空间复杂度 = O (递归层数)
最好空间复杂度 = O (log 2 n)
最坏空间复杂度 = O (n)
快速排序是所有内部排序算法中平均性能最优的排序算法
稳定性：不稳定
8.4 选择排序
8.4.1 简单选择排序
选择排序：每⼀趟在待排序元素中选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
简单选择排序： 每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列
空间复杂度：O (1)
时间复杂度 =O (n 2)
稳定性：不稳定
适⽤性：既可以⽤于顺序表，也可⽤于链表
8.4.2 堆排序
若 n 个关键字序列 L[1…n] 满⾜下⾯某⼀条性质，则称为堆（Heap）：
① 若满⾜：L (i)≥L (2 i) 且 L (i)≥L (2 i+1) （1 ≤ i ≤n/2）—— ⼤根堆（⼤顶堆）
② 若满⾜：L (i)≤L (2 i) 且 L (i)≤L (2 i+1) （1 ≤ i ≤n/2）—— ⼩根堆（⼩顶堆）
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列 （与待排序序列中的最后⼀个元素交换）并将待排序元素序列再次调整为⼤根堆 （⼩元素不断 “下坠”）
堆排序的时间复杂度 = O (n) + O (nlog 2 n) = O (nlog 2 n)
堆排序的空间复杂度 = O (1)
稳定性： 不稳定
8.4.3 堆的插入和删除
8.5 归并排序和基数排序
8.5.1 归并排序
归并：把两个或多个已经有序的序列合并成⼀个
排序算法：归并排序【图解+代码】_哔哩哔哩_bilibili
8.5.2 基数排序
空间复杂度 = O®
时间复杂度 = O (d (n+r)）
稳定性：稳定
基数排序擅⻓解决的问题：
①数据元素的关键字可以⽅便地拆分为 d 组，且 d 较⼩
②每组关键字的取值范围不⼤，即 r 较⼩
③数据元素个数 n 较⼤
8.6 内部排序算法比较与应用
8.7 外部排序
8.7.1 外部排序的基本概念
外部排序：数据元素太多，⽆法⼀次全部读⼊内存进⾏排序
“归并排序” 要求各个⼦序列有序，每次读⼊ 两个块的内容，进⾏内部排序后写回磁盘
外部排序时间开销 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间
8.7.2 败者树
k 路平衡归并：①最多只能有 k 个段归并为⼀个； ②每⼀趟归并中，若有 m 个归并段参与归并，则经过这⼀趟处理得到⌈m/k⌉个新的归并段
败者树——可视为⼀棵完全⼆叉树（多了⼀个头头）。K 个叶结点分别是当前参加⽐较的元素，⾮叶⼦结点⽤来记忆左右⼦树中的 “失败者”，⽽让胜者往上继续进⾏⽐较，⼀直到根结点
- 叶结点 当前参加比较的记录
- 内部结点 记忆左右子树中失败者的序号, 让胜者继续向上比较, 直到根结点
- 根结点 当前的最小数 / 最大数的序号, 不是数值本身 (胜者)
利用败者树得到最小值序号后, 取出最小值数, 在其位置加入下一个关键字, 继续比较, 构造败者树
使用败者树后, 比较次数与 m 无关, 可以增大 m 来减少归并树的高度
M 并不是越大越好 m 增大, 输入缓冲区增加, 其容量减少, 内外存交换数据的次数增大
8.7.3 置换选择排序
设初始待排⽂件为 FI，初始归并段输出⽂件为 FO，内存⼯作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 w 个记录。置换 - 选择算法的步骤如下：
1）从 FI 输⼊ w 个记录到⼯作区 WA。
2）从 WA 中选出其中关键字取最⼩值的记录，记为 MINIMAX 记录。
3）将 MINIMAX 记录输出到 FO 中去。
4）若 FI 不空，则从 FI 输⼊下⼀个记录到 WA 中。
5）从 WA 中所有关键字⽐ MINIMAX 记录的关键字⼤的记录中选出最⼩关键字记录，作为新的 MINIMAX 记录。
6）重复 3）～5），直⾄在 WA 中选不出新的 MINIMAX 记录为⽌，由此得到⼀个初始归并段，输出⼀个归并段的结束标志到 FO 中去。
7）重复 2）～6），直⾄ WA 为空。由此得到全部初始归并段。
8.7.4 最佳归并树
思想：让记录少的归并段最先归并, 记录多的最晚归并
重要结论：归并过程中的磁盘 I/O 次数 = 归并树的 WPL * 2
要让磁盘 I/O 次数最少，就要使归并树 WPL 最⼩ ——哈夫曼树！
注意：对于 k 叉归并，若初始归并段的数量⽆法构成严格的 k 叉归并树，则需要补充⼏个⻓度为 0 的 “虚段”，再进⾏ k 叉哈夫曼树的构造。
M 叉哈夫曼树：
- 叶结点参加归并的一个初始归并段
- 叶结点的权值初始归并段中的记录数
- 叶结点到根结点的路径长度归并趟数
- 非叶结点归并生成的新归并段
- 归并树的带权路径长度总读记录数
