目录
选择排序
简单选择排序
算法原理
性能
👩💻 堆排序
堆
顺序存储的“完全二叉树”
算法思想（以大根堆为例）
建堆
排序
特性
插入
删除
关键字对比次数
归并排序、基数排序
归并排序
👩💻 Merge（归并）
归并排序算法
性能
基数排序
算法思想
性能
擅长处理
外部排序
外部排序
败者树
置换-选择排序
最佳归并树
理论基础
如何虚构
补充虚段
选择排序
简单选择排序
算法原理
- 每一趟在待排序元素中选取关键字最小的元素加入有序子序列
- 必须进行总共n-1趟处理
性能
- 👩💻 时间复杂度：O(n^2)（始终是）
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用性：顺序表、链表都可以
👩💻 堆排序
堆
顺序存储的“完全二叉树”
- 结点i的左孩子是2i；右孩子是2i+1；父节点是i/2
- 编号≤n/2的结点都是分支节点
大根堆（根 ≥ 左、右）；小根堆（根 ≤ 左、右）
算法思想（以大根堆为例）
建堆
- 编号≤n/2的所有结点依次“下坠”调整（自底向上处理各分支节点）
- 👩💻 调整规则：小元素逐层“下坠”（与关键字更大的孩子交换）
排序
- 将堆顶元素加入有序子序列（堆顶元素与堆底元素交换）
- 堆底元素换到堆顶后，需要进行“下坠”调整，恢复“大顶堆”的特性
- 上述过程重复n-1趟
特性
- 空间复杂度：O(1)
- 时间复杂度：建堆O(n)、排序O（nlogn）；总的时间复杂度O(nlog2n)
- 稳定性：不稳定
- 基于大根堆的堆排序得到“递增序列”，基于小根堆的堆排序得到“递减序列”
插入
- 新元素放到表尾（堆底）
- 根据大/小根堆的要求，新元素不断“上升”，直到无法继续上升为止
删除
- 被删除元素用表尾（堆底）元素替代
- 根据大/小根堆的要求，替代元素不断“下坠”，直到无法继续下坠为止
关键字对比次数
- 每次“上升”调整只需对比关键字1次
- 每次“下坠”调整可能需要对比关键字2次，也可能只需对比1次
归并排序、基数排序
归并排序
👩💻 Merge（归并）
- 把两个或多个有序的子序列合并为1个
- 二路合并——二合一
- k路合并——k合一
归并排序算法
- 若low < high，则将序列分为从中间 mid = (low + high)/2分开
- 对左半部分[low,mid]递归地进行归并排序
- 对右半部分[mid+1,high]递归地进行归并排序
- 将左右两个有序子序列Merge为一个
性能
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(n)
- 稳定性：稳定的
基数排序
算法思想
- 将整个关键字拆分为d位（或“组”）
- 按照各个关键字位权重递增的次序（如：个 十 百），做d趟“分配”和“收集”，若当前处理的关键字位 可能取得r个值，则需要建立r个队列
- 分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列，一趟分配耗时O(n)
- 收集：把各个队列中的结点依次出队并链接，一趟收集耗时O(r)
性能
- 时间复杂度：O(d(n+r))
- 空间复杂度：O(r)
- 稳定性：稳定
擅长处理
- 数据元素的关键字可以方便的拆分位d组，且d较小
- 每组关键字的取值范围不大，即r较小
- 数据元素个数n较大
外部排序
外部排序
- 若要进行k路归并排序，则需要在内存中分配k个输入缓冲区和1个输出缓冲区
- 步骤
- 生成r个初始归并段（对L个记录进行内部排序，组成一个有序的初始归并段）
- 进行S趟k路归并，S = ⌈logkr⌉
- 如何进行k路归并
- 把k个归并段的块读入k个输入缓冲区
- 用”归并排序“的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中
- 当输出缓冲区满时，写出外存
- 时间开销：读写外存的事件 + 内部排序所需事件 + 内部归并所需时间
- 优化
- 增加归并路数k，进行多路平衡归并
- 代价1：需要增加相应的输入缓冲区
- 代价2：每次从k个归并段中选一个较小元素需要（k-1）次关键字对比（可用“败者树”减少关键字对比次数）
- 减少初始归并段数量r
- 增加归并路数k，进行多路平衡归并
败者树
- 解决的问题：使用多路平衡归并可减少归并趟数，但是用老土方法从k个归并段选出一个最小/最大元素需要对比关键字k-1次，构造败者树可以使关键字对比次数减少到**⌈log2k⌉**
- 败者树可视为一棵完全二叉树，k个叶节点分别对应k个归并段中当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根节点。
置换-选择排序
设初始待排文件FI，初始归并段输出文件为FO，内存工作区位WA，FO和WA的初始状态为空，WA可容纳w个记录。置换-选择算法的步骤如下：
- 从FI输入w个记录到工作区WA
- 从WA中选出其中关键字取最小值的记录，记录MINIMAX记录。
- 将MINIMAX记录输出到FO中去
- 若FI不空，则从FI输入下一个记录到WA中
- 从WA中所有关键字MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录
- 重复3-5，直至WA中选不出新的MINIMAX记录为止，由此得到一个初始段并段，输出一个归并段的结束标志到FO中去
- 重复2-6，直至WA为空。由此得到全部初始段并段。
最佳归并树
理论基础
- 每个初始段并段对应一个叶子结点，把归并段的块数作为叶子的权值
- 归并树的WPL = 树中所有叶节点的带权路径长度之和
- 归并过程中的磁盘I/O次数 = 归并树的WPL * 2
注意： k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的结点
如何虚构
补充虚段
- 若（初始归并段数量 - 1） % （k-1） = 0，说明刚好可以构成严格k叉树，此时不需要添加虚段
- 若（初始归并段数量 - 1） % （k-1） = u ≠ 0，则需要补充（k-1）- u个虚段
构造k叉哈夫曼树：每次选择k个根节点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值
