排序 | DS

基本概念

排序算法的稳定性

指经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变。

稳定性是对算法性质的描述，并不能衡量一个算法的优劣。

若待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关重要。

对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同（除非每个关键字唯一）。

排序算法的分类

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：

内部排序

指排序期间元素全部存放在内存中的排序。
外部排序

指排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

内部排序的比较与移动

一般情况下，内部排序算法在执行过程中基本要进行两种操作：比较、移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。

移动的方式分为两种：插入、交换。插入排序属于插入，交换排序、选择排序属于交换。交换往往使得算法不稳定（除冒泡），插入则不会（除希尔）。

插入会使得插入点及其后序全部元素后移一位；而交换则是每交换一次需要元素移动 3 次，因为需要借助中间变量。不过堆排序除外，输出堆顶后重新调整的移动次数在不超过树高的前提下，还与当前序列排列有关。

内部排序算法的时间复杂度一般是由比较和移动的次数决定的。

归并排序不基于移动（插入、交换），基数排序不基于比较和移动。

内部排序的比较次数

对任意 $n$ 个关键字排序的比较次数至少为 $\lceil \log_2(n!) \rceil$

对于任意序列进行基于比较的排序，求至少的比较次数应考虑最坏情况

在基于比较的排序方法中，每次比较两个关键字后，仅出现两种可能的转移。假设整个排序过程至少需要 $t$ 次比较，则显然会有 $2^t$ 种情况。由于 $n$ 个记录共有 $n!$ 种不同的排列，因而必须有 $n!$ 种不同的比较路径，于是有 $2^t \geq n!$，即 $t \geq \log_2(n!)$。

可以利用一棵二叉树来描述比较判定过程，由此可以证明：当文件的 $n$ 个关键字随机分布时，任何借助于 “比较” 的排序算法，至少需要 $O(n \log_2n)$ 的时间。

内部排序用到的存储结构

利用到随机存取特性的排序算法只适用于顺序存储的线性表（折半插入、希尔、快排、堆）。

而未利用到随机存取特性的排序算法同样亦适用于链表（直接插入、冒泡、简单选择、归并）。

内部排序

插入排序

共同特点：在最后一趟排序前，待排序列没有任何一个关键字到达其终点。

直接插入排序

排序过程：

查找出 L(i) 在 L[1…i-1] 中的插入位置 k；
将 L[k…i-1] 中的所有元素依次后移一个位置；
将 L(i) 复制到 L(k)。

折半插入排序

相较于直接插入排序的边比较边移动元素，折半插入排序将比较和移动操作分离，如此在查找有序子表时可以使用折半查找来提高查找效率。确定待插入位置后，就可统一地向后移动元素。

相较于直接插入排序仅减少了元素的比较次数，而元素的移动次数并未改变⚠。

希尔排序/缩小增量排序

直接插入排序更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点对直接插入排序进行改进而得来的。

基本思想

把相隔某个 “增量” 的记录组成一个子表 L[i,i+d,i+2d, …,i+kd]，对数据量不大的各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序

排序过程

先取一个小于 $n$ 的步长 $d_1$，这样表中的全部记录分成了 $d_1$ 组（$d_1 \leq n/2$ 时为 $d_1$ 组），在各组内进行直接插入排序；然后取第二个步长 $d_2 < d_1$，重复上述过程，直到所取到的 $d_t=1$，即所有记录已放在同一组，再进行直接插入排序。

时间复杂度

时间复杂度依赖于增量序列的函数，而目前尚未求得一个最好的增量序列，所以其时间复杂度分析比较困难。

当 $n$ 在某个特定范围时，希尔排序的时间复杂度约为 $O(n^{1.3})$。在最坏情况下时间复杂度为 $O(n^{2})$。

当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。

空间复杂度

O(1)。

交换排序

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序

基本思想

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 A[i-1] > A[i]），则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如同气泡一般逐渐往上 “漂浮” 直至 “水面”（或关键字最大的元素如石头一般下沉至水底）。下一趟冒泡时，前一趟确定的最小（或最大）元素不再参与比较，每趟冒泡的结果是把序列中的最小（或最大）元素放到了序列中的最终位置……这样最多做 $n-1$ 趟冒泡就能把所有元素排好序。

若在某趟没有发生交换，便跳出循环，此时全部元素已有序。

时间复杂度

当初始序列有序时，比较次数为 $n-1$，移动次数为 0，从而最好时间复杂度为 $O(n)$。

当初始序列逆序时，需要进行 $n-1$ 趟排序，第 $i$ 趟排序要进行 $n-i$ 次关键字的比较，每次比较后都必须移动 3 次来交换元素位置，故这种情况下比较次数为 $\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$，移动次数为 $\sum_{i=1}^{n-1} 3(n-i)=\frac{3 n(n-1)}{2}$，从而最坏和平均时间复杂度都为 $O(n^2)$。

空间复杂度

O(1)。

快速排序

基本思想

基于分治法、枢轴/基准 pivot（通常取首元素）、递归。

时间复杂度

与划分是否对称有关，最坏情况发生在两个区域分别包含 $n-1$ 个元素和 0 个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度 $O(n^2)$。

在最理想状态下，即 partition() 能做到最平衡的划分，得到的两个子问题的大小都不可能大于 $n/2$，在这种情况下，快速排序的运行速度将大大提升，此时时间复杂度为 $O(n\log_2n)$。

快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

有很多方法可以提高算法的效率：一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机的从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

空间复杂度

由于快排是递归的，因此需要借助一个递归工作栈来保存每层递归调用的必要信息。

递归工作栈容量与递归调用的最大深度一致。最好 $O(\log_2n)$；最坏 $O(n)$，因为要进行 $n-1$ 次递归调用；平均 $O(\log_2n)$。

稳定性

快排不稳定：在划分算法中，若右端区间有两个关键字相同且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化。如：3 2 2 → 2 2 3。

适用性

仅适用于顺序存储的线性表。

选择排序

每一趟（如第 $i$ 趟）在后面 $n-i-1$ 个待排序元素中选取关键字最小的元素，作为有序子序列的第 $i$ 个元素，直到第 $n-1$ 趟做完，待排序元素只剩下一个，就不用再选。

简单选择排序

基本思想

假设排序表为 L[1…n]，第 $i$ 趟排序从 L[i…n] 中选择关键字最小的元素与 L(i) 交换，每一趟排序可以确定一个元素的最终位置，这样经过 $n-1$ 趟排序就可使得整个排序表有序。

时间复杂度

移动次数：元素移动的操作次数很少，不会超过 $3(n-1)$ 次，最好的情况是移动 0 次，此时对应的表已经有序。

比较次数：元素间比较的次数与序列的初始状态无关，始终是 $n(n-1)/2$。

因此时间复杂度始终是 $O(n^2)$。

空间复杂度

O(1)。

稳定性

不稳定：在第 $i$ 趟找到最小元素后，和第 $i$ 个元素交换，可能会导致第 $i$ 个元素与其含有相同关键字元素的相对位置发生改变。如：2 2 1 → 1 2 2。

堆排序

堆的定义

$n$ 个关键字序列 L[1…n] 称为堆，当前仅当该序列满足：

① L(i) $\geq$ L(2i) 且 L(i) $\geq$ L(2i+1) 或

② L(i) $\leq$ L(2i) 且 L(i) $\leq$ L(2i+1)（$1 \leq i \leq \lfloor n/2 \rfloor$）

满足 ① 的堆称为大根堆/大顶堆，满足 ② 的堆称为小根堆/小顶堆

可将堆视为一棵完全二叉树⚠，大根堆的最大元素存放在根结点，且其任意一个非根结点的值小于等于其双亲结点值。小根堆则刚好相反。

堆排序思路

首先将存放在 L[1…n] 中的 $n$ 个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，再从堆顶元素向下调整使其保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中只剩一个元素为止。

如何将无序序列构造成初始堆？

$n$ 个结点的完全二叉树，从以第 $\lfloor n/2 \rfloor$ 个结点为根的子树开始筛选，使该子树成为堆（对于大根堆，若子树根结点的关键字小于左右孩子中关键字较大者，则交换），之后向前依次对各结点（$\lfloor n/2 \rfloor -1$ ~ $1$）为根的子树进行筛选。交换可能会破坏下一级的堆，需继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。
输出堆顶元素后，如何将剩余元素调整成新堆？

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。

和构造初始堆的向下筛选的算法是同一个，需要子结点间先比较⚠，选择出最大子结点（大根堆）再和父结点比较。
堆的插入与上浮

把新结点放到堆的末端，再对这个新结点向上调整。

一次上浮，子结点间不需要比较，只需和父结点比较⚠。最多和所有的父节点交换，共 $h-1$ 次，时间复杂度 $O(\log_2n)$。

时间复杂度

建堆时间为 $O(n)$，之后有 $n-1$ 次向下调整操作，每次调整的时间复杂度为 $O(h)$，故在最好、最坏、平均情况下，堆排序的时间复杂度为 $O(n\log_2n)$。

空间复杂度

O(1)。

稳定性

不稳定：进行筛选时，有可能把后面相同关键字的元素调整到前面。

如初始序列 1 2 2，构造初始大根堆 2 1 2，最终排序序列 1 2 2。

适用性

堆排序适合关键字较多的情况。

如在 1 亿个数中选出前 100 个最大值，首先用一个大小为 100 的数组，读入前 100 个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。

归并排序

归并：将两个或两个以上的有序表合并成一个新的有序表。

二路归并排序

基本思想

merge() 的功能是将前后相邻的两个有序表归并为一个有序表。

一趟归并排序的操作是，调用 $\lceil \frac{n}{2h} \rceil$ 次算法 merge()，将 L[1…n] 中前后相邻且长度为 $h$ 的有序段进行两两归并，得到前后相邻、长度为 $2h$ 的有序段。整个归并排序需要进行 $\lceil \log_2n \rceil$ 趟（$k$ 路归并则为 $\lceil \log_kn \rceil$ 趟）。

递归形式的二路归并算法是基于分治的。

时间复杂度

每趟归并的时间复杂度为 $O(n)$，共需进行 $\lceil \log_2n \rceil$ 趟，故时间复杂度为 $O(n \log_2n)$。

空间复杂度

需要一个与待排序表同等大小的辅助数组，故空间复杂度为 $O(n)$。

稳定性

merge() 操作不会改变相同关键字记录的相对次序，因此二路归并算法是一种稳定的排序算法。

适用性

适用于顺序存储和链式存储的线性表。

评价

从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用：先利用直接插入排序求得较长的有序子文件，然后两两归并。

直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。

基数排序

基本思想

一种借助多关键字排序的思想对单逻辑关键字进行排序的方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。

假设长度为 $n$ 的线性表中每个结点 $a_j$ 的关键字由 $d$ 元组（$k_j^{d-1},k_j^{d-2},…,k_j^1,k_j^0$）组成，满足 $0 \leqslant k_j^i \leqslant r-1$（$0 \leqslant j<n$，$0 \leqslant i \leqslant d-1$）。其中 $k_j^{d-1}$ 为最主位关键字，$k_j^0$ 为最次位关键字。

为实现多关键字排序，通常有两种方法：

最高位优先 (MSD) 法：按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。
最低位优先 (LSD) 法：按关键字位权重递增依次进行排序，最后形成一个有序序列。

以 $r$ 为基数的最低位优先基数排序的过程：

在排序过程中, 使用 $r$ 个队列 $Q_0,Q_1,…,Q_{r-1}$。对 $i=0,1,…, d-1$ 依次做一次 “分配” 和 “收集”（其实是一次稳定的排序过程）。

分配：开始时把 $Q_0,Q_1,…,Q_{r-1}$ 各个队列置成空队列，然后依次考察线性表中的每个结点 $a_j$（$j=0,1,…,n-1$）。若 $a_j$ 的关键字 $k_j^i=k$，就把 $a_j$ 放进 $Q_k$ 队列。
收集：把 $Q_0,Q_1,…,Q_{r-1}$ 各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。

时间复杂度

一趟分配需要 $O(n)$，一趟收集需要 $O(r)$，共需进行 $d$ 趟分配和收集，故时间复杂度为 $O(d(n+r))$，与序列的初始状态无关。

空间复杂度

一趟排序需要 $r$ 个队列（$r$ 个队头指针和 $r$ 个队尾指针），每趟排序重复使用，故空间复杂度为 $O(r)$。

稳定性

对于基数排序而言，很重要的一点就是按位排序时必须是稳定的。因此，这也保证了基数排序的稳定性。

适用性

虽然基数排序具有线性增长的时间复杂度，但由于在常规编程中，基数排序的线性时间开销实际上并不比快排的时间开销小很多，并且由于基数排序基于的关键字抽取算法受到操作系统和排序元素的影响，其适应性远不如普通的进行比较和交换操作的排序方法。因此在实际工作中，常规的高效排序算法如快排的应用要比基数排序广泛得多。

基数排序适用于顺序存储和链式存储的线性表。

计数排序*

基本思想

对每个待排序元素 x，统计小于 x 的元素个数，利用该信息就可确定 x 的最终位置。例如，若有 8 个元素小于 x，则 x 就排在第 9 号位置上。当有几个元素相同时，该排序方案还需做一定的优化。

计数排序也是一种不基于比较的排序算法。

在计数排序算法的实现中，假设输入是一个数组 A[n]，序列长度为 $n$，我们还需要两个数组：B[n] 存放输出的排序序列，C[k] 存储计数值。用输入数组 A 中的元素作为数组 C 的下标，例如对于数组 A 中的元素 x，C[x] 保存的是小于等于 x 的元素个数。

空间复杂度

计数排序是一种用空间换时间的做法。输出数组的长度为 n，辅助的计数数组长度为 k，空间复杂度为 O(n+k)。

若不把输出数组视为辅助空间，则空间复杂度为 O(k)。

k 取决于待排序元素的最大值。

时间复杂度

初始化计数数组 C 遍历了两次计数数组 C 和一次输入数组 A；最后遍历一次输入数组 A，根据计数数组 A 对应值将元素放在输出数组 B 的正确位置上。故共遍历了两次计数数组 C 和两次输入数组 A，总时间复杂度为 O(n+k)。

当 k = O(n) 时，计数排序的时间复杂度为 O(n)；但当 k ＞O(nlogn) 时，其效率反而不如一些基于比较的排序（如快排、堆排序等）。

稳定性

最后从后往前遍历输入数组，相同元素在输出数组中的相对位置不会改变，因此计数排序是一种稳定的排序算法。

适用性

适用于顺序存储线性表。

适用于序列中的元素是整数且元素范围（0 ~ k-1）不能太大，否则会造成辅助空间（计数数组）的浪费。

外部排序

外部排序和内部排序最主要的区别是是否涉及内存、外存的数据交换。

外部排序的方法

外部排序的两个阶段

根据内部缓冲区大小，将外存上的文件分成若干长度为 $l$ 的子文件，依次读入内存并利用内部排序的方法对它们进行排序，并将排序后得到的有序子文件重新写回外存。

这些有序子文件称为归并段或顺段。
对这些归并段进行逐趟内部归并，使归并段逐渐由小到大，直到得到整个有序文件为止。

外部排序过程

例如，待排序文件含有 2000 个记录，每个磁盘块可容纳 125 个记录。

首先经过 8 次内部排序得到 8 个初始归并段（长度 250 记录），再对这些初始归并段进行二路内部归并。

可以把内存工作区等分⚠成三个缓冲区，其中两个为输入缓冲区，一个为输出缓冲区。

二路归并流程：

1）从磁盘上的两个输入归并段 R1 和 R2 中分别读入一块放在内存输入缓冲区 1 和输入缓冲区 2。然后在内存中进行二路归并，归并后的对象顺序存放在输出缓冲区中。

2）若输出缓冲区中对象存满，则将其顺序写到磁盘上的输出归并段 R1‘ 中；若某个输入缓冲区中的对象取空，则从磁盘上对应的输入归并段中再读入下一块，继续参加归并。如此继续，直到两个输入归并段中的对象全部读入内存并都归并完成为止。

3）当 R1 和 R2 归并完后，再归并 R3 和 R4、R5 和 R6、R7 和 R8。自此完成第一趟归并。

4）把第一趟归并的结果 R1’ 和 R2’、R3’ 和 R4’ 两两归并，完成第二趟归并。

5）把第二趟归并的结果 R1‘’ 和 R2’’ 两两归并，完成第三趟归并，得到最终的有序文件。

磁盘读写次数

内部排序：8 次内部排序生成 8 个初始归并段，磁盘读写 32 次（读写各 16 次）。

内部归并：$\log_28=3$ 趟内部归并，每趟磁盘读写 32 次（读写各 16 次）。

磁盘读写总次数：$32+32 \times 3=128$ 次。

磁盘的读/写以磁盘块为单位。

外部排序总时间

外部排序总时间 = 内部排序所需时间 + 内部归并所需时间 + 外存信息读写时间。

外存信息读写时间远大于内部排序和内部归并所需时间，因此应着力减少 I/O 次数。

如何减少磁盘 I/O 次数

磁盘读写总次数 = 内部归并的趟数 $S \times$ 每趟归并进行磁盘 I/O 的次数 $+$ 内部排序进行磁盘 I/O 的次数。

而每趟归并进行磁盘 I/O 的次数和内部排序进行磁盘 I/O 的次数是固定的，等于 $\frac{文件大小}{磁盘块大小} \times 2$（内存允许的前提下），故减少磁盘 I/O 次数的途径为减少内部归并趟数 $S$。

如何减少内部归并趟数

对 $r$ 个初始归并段进行 $k$ 路归并，归并趟数 $S=\lceil \log_kr \rceil$，因此可以通过：

增大归并路数 $k$
减少初始归并段数量 $r$ → 产生更长的初始归并段 → 采用置换-选择排序生成初始归并段

两种方式减少归并趟数 $S$。

增大归并路数 $k$ 的消极影响：

增加每趟内部归并的时间

对于 $k$ 路归并，每得到归并后的有序段中的一个记录，都要进行 $k-1$ 次比较，显然为得到含 $u$ 个记录的归并段需进行 $(u-1)(k-1)$ 次比较（最坏情况）。由此，对含有 $n$ 个记录的文件进行外排时，在内部归并进行的总的比较次数为 $S(k-1)(n-1)=\lceil \log_kr \rceil (n-1)(k-1)=\lceil \frac{\log_2r}{log_2k} \rceil(k-1)(n-1)$

由于 $\frac{k-1}{\log_2k}$ 随 $k$ 的增长而增长，则内部归并时间亦随 $k$ 的增长而增长，这将抵消由于增大 $k$ 而减少外存信息读写时间所得效益。

解决方案：在进行 $k$ 路归并时利用败者树，可使总的比较次数与 $k$ 无关。
磁盘 I/O 次数增加

归并路数 $k$ 增加，相应地输入缓冲区数量增加，而内存工作区空间大小一定，势必要减少每个输入缓冲区的容量，减少到一定程度后，内部归并过程中磁盘 I/O 次数就开始增加（一个输入缓冲区放不下一个磁盘块，原本只需交换一次的信息数量现在需要多次），所以当 $k$ 值过大时，虽然归并趟数会减少，但读写外存的次数仍会增加。

多路平衡归并与败者树

败者树是树形选择排序的一种变体，可视为一棵完全二叉树⚠。

$k$ 个叶结点分别存放 $k$ 个归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右孩子结点中的 “败者”，而让 “胜者” 继续往上比较，一直到根结点。假设小者为胜，则根结点的双亲指向的数为最小数。

在选得最小关键字的记录之后，只要修改对应叶结点中的值，改为同一归并段中的下一个记录的关键字，然后从该结点向上和双亲结点所指的关键字进行比较，败者留在该双亲结点，胜者继续向上直至树根的双亲

为防止在归并过程中某个归并段变空，可在每个归并段中附加一个关键字为最大值的记录，当选出的 “冠军” 记录的关键字为最大值时，表明此次归并已完成。

败者树的初始化：所有的内部结点都指向一个含最小关键字的叶结点，然后从各个叶结点出发调整内部结点为新的败者即可。

因 $k$ 路归并的败者树深度为 $\lceil log_2k \rceil$ + 1，因此 $k$ 个记录中选择最小关键字，最多需要 $\lceil \log_2k \rceil$ 次，所以总的比较次数为 $S(n-1)\lceil \log_2k \rceil=\lceil \log_kr \rceil(n-1)\lceil \log_2k \rceil=(n-1) \lceil \log_2r \rceil$。可见，使用败者树后，内部归并的比较与 $k$ 无关了，因此，只要内存空间允许⚠，增大归并路数 $k$ 将有效地减少归并树的高度（归并趟数），从而减少 I/O 次数，提高外部排序的速度。

置换-选择排序

前面说过，除了增大归并路数 $k$ 能够减少内部归并趟数外，减少初始归并段数量 $r$ 也能减少内部归并趟数。初始归并段数量减少意味着初始归并段更长，而采用内部排序得到的各个初始归并段长度都相同（除最后一段），它依赖于内部排序时可用内存工作区的大小。因此必须探索新的方法来产生更长的初始归并段，这就是本节要讨论的置换-选择算法。

置换-选择排序是在树形选择排序的基础上得来的，它的特点是：在整个排序的过程中（得到所有初始归并段），最小或最大关键字的选择和输入、输出交叉或平行进行。

设初始待排文件为 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 为空。由此得到全部初始归并段。

在 WA 中选择 MINIMAX 记录的过程利用败者树实现（了解即可）：

1）内存工作区中的记录作为败者树的外部结点，而败者树中根结点的双亲结点指示工作区中关键字最小的记录。

2）为每个记录附设一个所在归并段的序号，在进行关键字的比较时，先比较段号，段号小者为胜；段号相同的则关键字小者为胜。

3）败者树的建立可从设工作区中所有记录的段号均为零开始，然后从 FI 逐个输入 $w$ 个记录到工作区时，自下而上调整败者树，由于这些记录的段号为 1，则它们对于 0 段的记录而言均为败者，从而逐个填充到败者树的各结点中去。

最佳归并树

文件经过置换-选择排序后，得到的是长度不等的初始归并段。下面讨论如何组织长度不等的初始归并段顺序，使得 I/O 次数最少。

归并树中，各叶结点表示一个初始归并段，权值表示归并段长度（即记录数），叶结点到根的路径长度表示其参加归并的趟数，各非叶结点代表归并成的新归并段，根结点表示最终生成的归并段。树的带权路径长度 WPL 为归并过程中总外存读或写的次数（假设每个记录占一个物理块），故 I/O 次数 = 2 × WPL。

显然归并方案不同，所得归并树亦不同，WPL 亦不同。对 $r$ 个长度不等的初始归并段构造一棵 $k$ 叉哈夫曼树作为归并树（WPL 最小），便可使在进行外部归并时磁盘 I/O 次数最少，这棵归并树便称作最佳归并树。

实现 $k$ 路平衡归并的最佳归并树可能需要添加若干长度为 0 的虚段（$k>2$）。详见第五章哈夫曼树一节。

刷题总结

快排

速度最快：枢轴均分

速度最慢：有序

每趟比较次数：长度大于 1 的子表关键字总数 - 长度大于 1 的子表数

移动次数：按算法走一遍

每趟排序都会将至少一个元素（枢轴）放置到其最终的位置上（对尚未确定最终位置的所有元素进行一遍处理称为一 “趟”），每趟有几个子表就有几个枢轴会被放置到最终位置上。
冒泡

不要以为每趟冒泡只是最小/大关键字冒泡，实际上遍历过程中遇到逆序对就会发生交换。

最少趟数：通常在每趟排序的过程中会判断是否产生新的逆序对，若不会产生，则说明本趟的序列已经全局有序。这种方式下最后一趟是无交换的排序，计算最少趟数时默认要加上。
堆排序

建立初始堆：O(n)，不超过 4n。

自顶向下调整一次/删除一个结点后调整：O($log_2n$)，子结点要先比较一次以选出最小/大的结点再跟父结点比较⚠。

取得第 k 个最小/大元素之前的排序所花时间为：O($klog_2n$)，总时间为 4n + O($klog_2n$)。

插入一个结点后上浮调整：O($log_2n$)，子结点之间不需要比较，上浮一层只需跟父结点比较一次⚠。
在基于比较的排序算法中，只有冒泡、选择（简单选择、堆）每趟都确定一个最小的元素，每趟最左生成全局有序子表（升序），而插入、快排、归并只有在将元素全部排完序后才能得到前 k 个最小的元素序列。

选出 k 个最小元素耗时：堆（4n + $klog_2n$）、冒泡（kn）、简单选择（kn），当 k ≥ 5 时，可以得出堆排序最优。
堆是棵完全二叉树，从根结点到任意叶结点的路径都是有序的。

既是堆又是二叉排序树的非空二叉树只能是：① 只有根结点；② 只有两个结点的左斜单支树。
问时间复杂度默认为最坏。
多关键字排序，优先级低的先排，且从第二个使用的排序算法开始就需要是稳定的，不然会打乱前面的排序。
关键字为实数时可以使用基数排序❌

基数不能对浮点数进行排序。
堆的定义是递归的，故小(大)根堆的次小(大)值一定在根的下一层

小(大)根堆最大(小)值一定在叶结点，即范围为 $\lfloor n/2\rfloor+1$ ~ $n$
快排是最通用的高效内部排序算法。
将两个各有 N 个元素的有序表合并成一个有序表，最少的比较次数是 N，最多的比较次数是 2N - 1。

将两个各有 M、N 个元素的有序表合并成一个有序表，最少的比较次数是 min(M, N)，最多的比较次数是 M + N - 1。

将两个各有 M、N 个元素的有序表合并成一个有序表，当一个表为空时，另一个表剩余元素数为 x（x ≥ 1），比较次数为 M + N - x。
可以并行执行：快排、堆、归并。
交换排序、选择排序属于交换，其中一般简单选择交换次数最少。
在做 $m$ 路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置 2$m$ 个输入缓冲区和 2 个输出缓冲区。

一般同步处理时，需要 $m$ 个输入缓冲区和 1 个输出缓冲区。
败者树是一棵完全二叉树。无论是几路归并，它都是二叉。

败者树 = 多路平衡归并。

$m$ 路平衡最佳归并树（败者树 + 最佳归并树），表面是严格 $m$ 叉，“放大” 每个分支结点及其孩子结点，实际是完全二叉。