408数据结构-排序

1. 基本概念

稳定性：如果待排序序列中存在两个相同的关键字，排序前后相同关键字之间的前后关系不变，那么算法就是稳定的，反之则是不稳定的。

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

• 内部排序：排序期间元素全部存放在内存中的排序
• 外部排序：排序期间元素无法同时存放在内存中

并非所有的排序算法都基于比较操作（比如基数排序，计数排序）。

比较次数

对于任意 $n$ 个关键字，进行基于比较的排序，比较次数至少为 $\left \lceil \log_2(n!) \right \rceil$。

证明：

进行基于比较的排序时，尽可能出现两种可能的转移（即形成两种新的排列状态）。假设整个排序过程至少要做进行 $t$ 次比较，那么显然整个排序的过程总共会生成 $2^t$ 个状态。当 $2^t\ge n$ 时，已经是搜索到了最终排好序的状态的。于是 $t\ge \log_2(n!)$，最少比较次数为 $\left \lceil \log_2(n!) \right \rceil$。

题目中的“一趟”

• 对于插入排序，一趟就是将某个元素不断往前插的过程。注意第一个元素的插入不算躺（上来就从 $i=2$ 开始）。也就是元素经过 $n$ 躺后，序列的一端有 $n+1$ 个元素是排好序的。
• 对于希尔排序，一趟就是在某个增量下的全部操作。
• 对于快速排序/归并排序，一趟就是在递归树上的一层的全部操作。
• 对于冒泡排序，往往需要额外的一趟来判断整个序列是否已经全局有序。
• 对于堆排序，考虑堆排序是一种选择排序，所以一趟就是从堆顶选择一个结点的过程。
• 对于 $k$ 路归并排序，第一趟排序将会在序列中每 $k$ 个元素合并成一个表，得到 $\left \lceil \frac{N}{k} \right \rceil$ 个表，然后再每 $k$ 个表合并成一个大表...，以此类推。

2. 内部排序

2.1 插入排序

2.1.1 直接插入排序

序列的前面部分是排好序的，后面部分是尚未排序的。每次将尚未排序的部分的第一个元素，尝试插入到前面的有序序列中。将要插入位置之后的元素往后移动一个位置，然后再插入进去。

下图中的算法相当于是一边往后移动一边寻找插入的位置

空间复杂度 $O(1)$

时间复杂度：

• 最好情况：如果原来的序列已经有序了，那么时间复杂度为 $O(n)$
• 最坏情况：如果原来的序列和要排成的顺序是相反的，那么时间复杂度为 $O(n^2)$
• 平均情况：$O(n^2)$

稳定性：稳定

适用性：适用于顺序存储和链式存储的线性表。采用链式存储时无需移动元素。

比较次数：需要注意以下几点

• 虽然代码为了实现方便，设置了“哨兵”元素，但是计算比较次数的时候不考虑哨兵元素。
• 第一个元素不用算比较次数
• 如果当前元素比较大，不向前插入，那么比较次数是 $1$
• 其他元素的比较次数有两部分：由于比较而向前移动的比较次数，以及由于比较而停止移动的比较次数（同样也是注意不考虑和哨兵元素的比较）

2.1.2 折半插入排序

在直接插入排序的基础上，插入的时候可以考虑使用折半查找来找到要插入的位置。

仅是把比较的次数从 $O(n^2)$ 降低到 $O(n\log n)$。总的时间复杂度还是 $O(n^2)$。对于数据量不大的排序表，折半插入排序往往能表现出良好的性能。

折半插入排序仅适用于顺序存储的线性表。

比较次数：折半插入排序的二分部分的比较次数似乎是和序列的初始状态无关的。

2.1.3 希尔排序

先准备一个增量序列 $d_i$，然后对序列的不同部分进行多次插入排序。

比如序列长度为 $10$，则 $d_i = 5,2,1$ （取序列长度的一半，然后增量序列逐渐砍半）。第一次插入排序，从第一个元素开始，每隔 $5$ 个元素取一个元素，对这些间隔的元素进行插入排序。然后从第二个元素开始，每隔 $5$ 个元素取一个元素，进行插入排序...在增量为 $5$ 时可以总共取出 $5$ 子序列。然后再每隔 $2$ 个元素取一个元素...，最后每隔 $1$ 个元素取一个元素....，这样就完成了整个的排序。

空间复杂度：$O(1)$

时间复杂度：希尔排序的时间复杂度依赖于增量序列的函数。一般就是不断取一半。希尔排序的时间复杂度分析较为困难，这里只给出结论

• 最好情况：$O(n)$
• 最坏情况：$O(n^2)$
• 平均情况：开始时序列无序程度比较大，但是元素数量较小，所以耗费时间较小。到后面元素数量较大时，序列也由于之前的部分插入排序而变得有序，接近了插入排序的最好情况。综合起来，平均时间复杂度为 $O(n^{1.3})$
• 实际上希尔排序还是并没有很精确的复杂度分析，在题目中，并不讨论希尔排序的任何时间复杂度（无论是最好、最坏还是平均）

第三个空不选希尔排序

稳定性：不稳定

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

2.2 交换排序

2.2.1 冒泡排序

从前往后两两比较元素，若为逆序，则交换，直到序列比较完。此时最大的关键字将会被放到最后面。多进行几轮就完成了排序。

需要加上当前已经排好序的优化

冒泡排序产生的子序列一定是全局有序的，即每趟排序都会将一个元素放置到其最终的位置上。而插入排序则没有这种性质。

空间复杂度：$O(1)$

时间复杂度：

• 最好情况：$O(n)$
• 最坏情况：$O(n^2)$
• 平均情况：$O(n^2)$

稳定性：注意，冒泡排序的算法中，如果比较两个关键字相等，那么是不会交换这两个关键字。因此冒泡排序是稳定的。

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

移动次数：一个交换隐含着 $3$ 次数据移动，因此最坏情况下元素移动次数为 $3(n-1)$。

2.2.2 快速排序

基于分治。在待排序表中选取任意一个元素作为 pivot（或称枢轴/基准）（通常取首元素）。然后再对整个排序表进行遍历，将其划分成两部分，左边部分的元素都小于等于 pivot，右边部分的元素都大于等于 pivot，然后再把 pivot 放到中间，然后再递归地去对左右两部分进行操作。

注意，当选择 low 为 pivot 的时候，low 这个位置的数字相当于已经被移走，low 这个位置就是个空位了。所以，我们进入 while 循环后，一定是先不断在 high 那里找小于等于 pivot 的元素，找到之后就可以将其放入 low 那里的空位上，然后 high 这里又有了空位，于是再不断在 low 那里找大于等于 pivot 的元素放到 high 那里的空位，以此类推....

空间复杂度：快速排序是递归的，需要用栈作为辅助空间。

• 最好情况：递归层数最少，为 $O(\log n)$
• 最坏情况：需要递归 $n-1$ 次，为 $O(n)$
• 平均情况：$O(\log n)$

时间复杂度

• 最好情况：$O(n\log n)$
• 最坏情况：初始的序列基本有序或者是基本逆序，此时为 $O(n^2)$
• 平均情况：算法的效率主要取决于 pivot 的选取，有很多选取方法，比如从序列的头尾和中间三者中选取一个中间的元素作为 pivot，又或者是随机地选取 pivot，这都可以使得最坏情况在实际排序中几乎不会发生。所以平均时间复杂度是 $O(n\log n)$

稳定性：在划分中，如果右端区间有两个关键字相同，且都小于 pivot，那么就会被交换到左端区间，那么相对位置就会发生变化。因此快速排序是不稳定的。

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

快速排序是所有内部排序算法中平均性能最优的排序算法。

快速排序算法中并不像插入排序和冒泡排序那样产生有序的子序列，但是会确保，每次划分完左右区间后，pivot 会放到最终的位置上。

比较次数：

2.3 选择排序

2.3.1 简单选择排序

维护一段已经排好序的前缀。算法每次会从序列后面部分中寻找一个最小值，然后把这个最小值与前面的元素进行交换，延申已经排好序的前缀。

注意，如果最小值在最左边，那么就不再进行交换。以及只需要进行 $n-1$ 趟。

空间复杂度：$O(1)$

时间复杂度：$O(n^2)$

稳定性：不稳定。比如 $\left\{ 2, \mathbf{2}, 1 \right\}$，把 $1$ 交换到前面之后：$\left\{ 1, \mathbf{2}, 2 \right\}$

适用性：顺序存储和链式存储的线性表均可以

2.3.2 堆排序

一般直接在线性表上建堆。堆可视为一个完全二叉树。线性表下标从 $1$ 开始。对于 $k$ 位置的结点，$2k$ 位置为其左子节点，$2k+1$ 位置为其右子节点。

对于大根堆，需要满足父节点大于等于其子节点。小根堆同理。

建堆

对于 $n$ 个结点的二叉树，最后一个结点的父节点编号是 $\left \lfloor \frac{n}{2} \right \rfloor$，因此从 $\left \lfloor \frac{n}{2} \right \rfloor$ 到 $1$ 结点依次进行调整。每次调整时，如果子节点比父节点大，那么就把父节点的值和最大子节点的进行交换。有可能交换之后，子节点所对应的堆又不满足堆的要求了，可能还需要递归地重新调整子节点。

删除

把最后一个元素替换掉堆顶元素，然后再对整个堆进行调整：

最后一个元素是9

插入

在堆的结尾插入一个新的节点，然后不断向上调整堆。（一般情况下说维护堆，不考虑插入这个操作，视为仅是从上往下维护堆）

空间复杂度：$O(1)$

时间复杂度：

• 建堆：$O(n)$
• 删除/插入元素：$O(\log_2n)$
• 堆排序：删除 $n-1$ 次。$O(n\log_2n)$

稳定性：不稳定

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

比较次数：注意，在调整时，如果左右子节点均非空，那么是先让左右子节点之间比较，然后较大的那个再和当前结点比较。如果只有左子节点，那么就是直接和左子节点比较。

在海量数据中选出最小的 $k$ 个数

比如在 1 亿个数中选出前 100 个最大值。首先开大小为 100 的数组，读入前 100 个数，建立小根堆。然后依次读入余下的数，如果小于堆顶则直接舍弃，否则该数替换掉堆顶并重新调整堆。这样做完之后堆中的 100 个数即为所求。

2.4 其他排序算法

2.4.1 归并排序

对于二路归并排序，有：

空间复杂度：合并的时候需要使用到辅助空间，空间复杂度为 $O(n)$

时间复杂度：

• 每趟归并排序的时间复杂度为 $O(n)$
• 共需要进行 $\left \lceil \log_2n \right \rceil$ 躺归并
• 总的时间复杂度为 $O(n\log_2n)$

稳定性：稳定

适用性：不仅可以用于顺序存储的线性表，也可以用于链式存储的线性表

比较次数：一趟排序的比较次数包含所有合并时的比较次数。对于某次合并，假设是二路归并，那么当一个子表的元素全部归并完了之后，后续的归并就不再产生比较次数了。因此，二路归并时，假设一个线性表大小为 $N_1$，另一个线性表大小为 $N_2$，单就归并这一个操作，最好情况是 $O(\min (N_1,N_2))$，最坏情况是 $O(\max(N_1,N_2))$。

对于 $N$ 个元素进行 $k$ 路归并排序时，排序的躺数 $m = \left \lceil \log_k N\right \rceil$

2.4.2 基数排序

基数排序不基于比较和移动。基数排序借助多关键字排序的思想来对单逻辑关键字进行排序。

假设长度为 $n$ 的线性表中每个节点 $a_i$ 的关键字由 $d$ 元组 $\left (k_i^{d-1}, k_i^{d-2}, \dots , k_i^0\right)$ 组成，其中 $k_i^0$ 为最次位关键字，$k_i^{d-1}$ 为最主位关键字。

基数排序有两种多关键字排序方法：MSD 法和 LSD 法。

LSD 法

按关键字权重递增的顺序依次排序。假设每个关键字的值域为 $[0,r-1]$，在排序过程中，使用 $r$ 个队列 $Q_0, Q_1, \dots Q_{r-1}$，然后对 $i=0,1,\dots, d - 1$ 依次做一次分配和收集：

• 分配：开始时，把队列 $Q_0, Q_1, \dots Q_{r-1}$ 各个队列清空，然后对于线性表中的每个节点，如果该节点的关键字 $k^{i} = x$ ，就把该节点放到队列 $Q_x$ 队列中。
• 收集：把 $Q_0, Q_1, \dots Q_{r-1}$ 各个队列中的结点依次首尾相接，得到新的线性表。

比如：

在算法竞赛中经常这样写代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
constexpr int N = 100010;
constexpr int W = 100010;
constexpr int K = 100;

int n, w, k, cnt[W];

struct Element {
  int key[K];
} a[N], b[N];

void counting_sort(int p) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i].key[p]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  // 为保证排序的稳定性，此处循环i应从n到1
  // 即当两元素关键字的值相同时，原先排在后面的元素在排序后仍应排在后面
  for (int i = n; i >= 1; --i) b[cnt[a[i].key[p]]--] = a[i];
  memcpy(a, b, sizeof(a));
}

void radix_sort() {
  for (int i = k; i >= 1; --i) {
    // 借助计数排序完成对关键字的排序
    counting_sort(i);
  }
}

上述代码将上面思路中各个队列合到一个数组中（b[i]），然后预先计算好每个队列会存的元素的大小 cnt[i] ，然后做前缀和，此时 cnt[i] 就表示关键字 i 将要被存放的位置。上面代码中调用一次 counting_sort 相当于一趟排序。基数排序需要进行多趟排序。

空间复杂度：一趟排序需要的辅助存储空间为 $r$（$r$ 个队列，包含 $r$ 个头指针和 $r$ 个尾指针）。$O(r)$

时间复杂度：基数排序需要进行 $d$ 躺排序，一趟排序需要遍历所有的关键字，耗费 $O(n)$ 时间，然后合并 $r$ 个队列，耗费 $O(r)$ 时间。总共为 $O(d(n+r))$。

稳定性：稳定。

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

MSD 法

这种方法比 LSD 更直接，直接先排序第一关键字，第一关键字相同的结点再递归排第二关键字，相当于多次计数排序。

MSD 适用于每个结点的关键字个数不同，比如字符串这种。

2.4.3 计数排序

计数排序也不基于比较。

代码思路和上面 LSD 基数排序的思路相同

空间复杂度：令 $v$ 为关键字排序。$O(n+v)$，其中 $O(n)$ 表示的是输出数组的空间。如果将输出数组视为辅助空间，那么空间复杂度为 $O(v)$。

时间复杂度：$O(\max(n,v))$。$v>O(n\log n)$ 时计数排序不如一些基于比较的排序。

稳定性：稳定

适用性：更适用于顺序存储的线性表（感觉链式存储也没问题），且关键字全为整数，且关键字不能太大。

2.5 排序算法比较

时空效率

算法选择

• 如果 $n$ 比较小，可以使用直接插入排序或简单选择排序。这两者中简单选择排序的移动次数更少一点，因此如果待排序的数据本身信息量比较大的时候，简单选择排序会更好。
• 如果 $n$ 比较大，应当使用 $O(n\log_2 n)$ 的算法：快速排序、堆排序、归并排序。关键字随机分布的时候，快速排序是最快的。堆排序将不会出现快速排序的最坏情况。归并排序是这三者中唯一的稳定的算法。
• 如果 $n$ 比较大，关键字比较小，或是关键字可分解，那么采用基数排序较好。
• 对于一个基本有序的序列，选择直接插入排序是比较好的（冒泡排序次之）。

这个性质也可以用来大致排除选项，比如B和C接近有序（一个理由是较大的元素都在后面），排除A和D

冒泡排序、简单选择排序、堆排序、快速排序，都能做到每趟确定一个元素的最终位置。而插入排序不能。其中冒泡排序、简单选择排序、堆排序可用于高效地求前 $k$ 个最小元素。

简单选择排序的比较次数与序列初始状态无关。归并排序的比较次数与序列初始状态有关，但是比较次数的数量级是与初始状态无关的。基数排序不基于比较和移动，因此比较次数也和初始状态无关。

而对于移动次数，基数排序和归并排序应该是和初始状态无关的，简单选择排序应该还是有关的（如果最值就在最左侧，那么就不移动了）

3. 外部排序

当对大文件内的数据进行排序时，可能无法将整个文件放入内存中，排序时只能将文件中的数据一部分一部分读入内存。

外部排序需要进行文件读写。IO 读写时间远大于 CPU 的运算时间，因此外部排序中的时间代价主要考虑 IO 次数。

3.1 多路归并

外部排序一般是基于归并排序。首先把待排序的大文件分成多个小文件，然后先把每个小文件读进来，进行内部排序。然后，再开两个输入缓冲区，同时读入两个小文件，进行归并排序，将其输出到输出缓冲区。

注意，把两个小文件读入进来的时候并不是把整个一块读进来，而是每次只读缓冲区大小的数据。

磁盘 IO 是以“磁盘块”为单位的。假设这个大文件占用了 $N$ 个磁盘块，对 $r$ 个初始归并段，做 $k$ 路归并，那么一共需要 $S = \left \lceil \log_kr \right \rceil$ 躺归并，需要 $2\cdot(SN+N)$ 次 IO（乘 $2$ 是因为每次读完还要写，里面还加了 $N$ 是初始归并段内部排序的 IO）。

降低 $S$ 可以减少 IO 次数。一方面可以减少 $r$（减少初始归并段），另一方面可以增大 $k$（增大归并路数）。

计数问题

如果磁盘上每个块可以放 $B$ 个记录，内存区可以容纳 $M$ 记录，那么可以进行 $M/B-1$ 路归并。（减 $1$ 是用于输出缓冲区）

3.2 败者树

如果 $k$ 太大的话，IO 次数少了，但是每次多路选择一个最值时，耗费的比较次数就会比较多，是 $O(k)$ 的。解决方案是使用败者树。

败者树是一个二叉树，叶子节点记录其对应的缓冲区的顶部的元素。然后从下往上，非叶结点上判断两个子结点中谁的元素是最值，记录其对应的缓冲区的编号（图中没画）。同时还记录左右结点不是最值的缓冲区编号（被称为是“败者”。图中圆形结点内部记录的是这个）。

首次建立败者树将会消耗 $O(k)$ 的时间。我们可以从败者树的根节点上得到当前最值所处的缓冲区的编号，然后将其从缓冲区中删除。随后，该缓冲区新到顶部的元素将会从败者树的底部向上更新败者树。由于每个非叶结点已经记录了上一步的败者，所以新元素可以直接和上一次的败者比较，得到获胜者以及可能更新败者，这个过程是 $O(\log k)$ 的。

然后我们不太严谨地计算一下。对于 $n$ 个元素，每趟归并需要进行 $(n-1)\left\lceil \log_2k \right \rceil$ 次比较，那么总共需要比较次数为：

$$S(n-1)\left \lceil \log_2k \right \rceil = \left \lceil \log_kr \right \rceil (n-1) \left \lceil \log_2k \right \rceil = (n-1)\left \lceil \log_2r \right \rceil$$

可见，使用败者树的话，归并的比较次数就与 $k$ 无关了。

但是 $k$ 仍然不是越大越好，因为 $k$ 越大，所需要的缓冲区内存越多。

3.3 置换-选择排序

我们上面提到，减少初始归并段也可以提高效率。但我们上面的做法产生的初始归并段不会超过内存大小。

置换-选择排序则可以让我们产生的初始归并段大小，在最坏情况下是内存大小，在平均情况下是内存大小的两倍，在最好情况下是整个数据的大小。

假设我们的内存可以容纳 $w$ 个关键字，那么置换-选择排序在最开始，会将输入文件的前 $w$ 个关键字读到内存里。然后，从 $w$ 个关键字中选择最小值，放到输入文件中，同时记其为 $MINIMAX$。然后再把输入文件的下一个关键字在内存中替换掉刚才的 $MINIMAX$。然后再从内存中选择，大于等于 $MINIMAX$ 的最小值，放到输出文件中，并作为新的 $MINIMAX$，然后继续重复这个过程。

如果内存中的元素都小于 $MINIMAX$ 了，那么就把已经输出的部分作为一个段。

由于放入内存中的数字可能非常多，因此需要一个比较快寻找全局最小值的数据结构来维护。王道的书上说用败者树，但是败者树似乎不好实现查找大于某个值的最小值。而这个问题其实还可以使用平衡树来解决。

3.4 最佳归并树

经过置换-选择排序算法得到的初始归并段可能长度不一。直接进行朴素的归并排序可能效率不高：

如果某个叶子结点到根结点的距离为 $l$，那么就说明这个结点所对应的初始归并段对于整个归并过程贡献了 $2l$ 的 IO 次数（一读一写）。

那么现在就转化成了哈夫曼树问题，我们需要让树的 $WPL$ 尽可能低，$2WPL$ 就是完成整个排序需要的 IO 次数。如果我们使用 $k$ 路归并，那么最后需要得到一个只有 $0$ 度和 $k$ 度结点的哈夫曼树，我们称其为 $k$ 路平衡归并的最佳归并树。

但是还需要注意。比如上面的图中是 $9$ 个初始归并段，如果变成 $8$ 个初始归并段，就无法确保构成一个三叉树了。于是我们需要添加长度为 $0$ 的虚段。

设 $0$ 度的结点有 $n_0$ 个，度为 $k$ 的结点有 $n_k$ 个。$n$ 为总结点个数，那么就有：

$$\begin{align} n &= n_k + n_0 \\ n &= kn_k + 1 \end{align}$$

于是就有 $n_0 = (k-1)n_k + 1$，也就有 $n_k=\frac{n_0 - 1}{k-1}$。

• 如果 $(n_0-1)\%(k-1)=0$，那么初始归并段刚好可以构成一个 $k$ 叉归并树
• 如果 $(n_0-1)\%(k-1)=r$，那么说明我们需要 $\left\lceil \frac{n_0-1}{k-1} \right\rceil$ 个度为 $k$ 的结点，然后再根据此算出需要的 $n_0$，算出需要补的虚段的数量

4. 错题

我甚至问了 AI，AI 也无法给出不再进行额外一轮比较即可判断序列已经有序的做法。我怀疑题目是错的。

看起来冒泡排序只需要一躺就完成了排序，但实际上还需要再来一趟已确定排序完毕，这样的话就不如插入排序优了。

堆排序的左右结点内的操作还是可以并行的。

直接考虑简单选择排序

注意看清楚是比较次数还是移动/交换次数。

输入和输出缓冲区都要增加一倍。这样可以做到，归并算法输出到一个缓冲区的同时，另一个输出缓冲区的内容写入到磁盘上。对于输入也是同理。

$m$ 与 $n$ 有关，但是并非正比反比这种直接的关系。

O(n)设计算法

类似快速排序那样，双指针，相互交换即可 $O(n)$

仍然可以类似快速排序的思想，做到 $O(n)$

还是类似快速排序那种交换的思想做到 $O(n)$。

j 当前元素，i 之前（不含 i）均为红色，k 之后（不含 k ）均为蓝色。

算法会将红色全部抛到左边，蓝色全部抛到右边。使用交换的方式进行移动，使得尚未排序的元素全部聚集到中间。

由于红色部分就是聚集在前面的，因此代码中 RED 有 j++。蓝色部分是聚集在后面的，有可能交换时，交换的两个元素都是蓝色，于是代码中 BLUE 没有 j++。

类似于第二题那样：