第五讲 Sorting

第五讲 排序（Sorting）

稳定性：相同关键码元素的固有顺序在排序前后不改变；

原地性：除输入外使用的额外空间为\(O(1)\)。

选择排序（Selection Sort）

  • \(i:1\to n-1,j=i,k:i+1\to n\)
  • 若\(A_k<A_j\)，则\(j\gets k\)
  • \(\text{Swap}(A_i,A_j)\)

即对每个\(A[i]\)，\(A_i\gets\min\{A_i,A_{i+1},\cdots ,A_n\}\)

原地但不稳定，例如\([5_a,5_b,2]\)，选择排序后得到\([2,5_b,5_a]\)

冒泡排序（Bubble Sort）

  • \(i:n\to 2,j:1\to i-1\)
  • 若\(A_j>A_{j+1}\)，则\(\text{Swap}(A_j,A_{j+1})\)

原地且稳定

堆排序（Heap Sort）

原地但不稳定，例如\([2_a,2_b,1]\)，堆排序后得到\([1,2_b,2_a]\)

归并排序（Merge Sort）

不原地但稳定

快速排序（Quick Sort）

  • 选择\(x\)作为界限

  • 分割序列为\(A[1,\cdots,k],A[k+1,\cdots,n]\)，前一序列元素均不大于\(x\)，\(A[k]=x\)，后一序列均大于\(x\)

  • 对前后两序列递归

Question 1：怎么在选取了界限的基础上将原序列分为前后两半？

方法一：设置新数组，从前往后填比\(x\)小的，从后往前填比\(x\)大的，但如此丧失了原地性。

方法二：考虑界限为\(x=A[k]\)，将其与\(A[n]\)交换。

维护两个子序列\(A[1,\cdots,i],A[i+1,\cdots,j]\)，其中\(A[1,\cdots,i]\leqslant x,A[i+1,\cdots,j]>x\)。

初始化\(i=j=0\)。

  • 若\(A[j+1]\leqslant x\)，交换\(A[i+1],A[j+1],i\gets i+1,j\gets j+1\)；

  • 否则，\(j\gets j+1\)；

  • 若\(j=n-1\)，交换\(A[i+1],A[n]\)，结束算法。

时间复杂度为\(O(n)\)（画一个示意图感受一下）

Question 2：怎么选取界限？

如果粗浅地选用第一个元素作为界限，最坏时间复杂度为\(O(n^2)\)，考虑随机选取界限。

Proof 1:递归证明与数学归纳法

时间复杂度\(T(n)\)满足$\(T(n) = T(k-1) + T(n-k) + O(n)\)$

假设划分的左右界限\((1,k-1),(k+1,n)\)是等概率出现的，概率为\(1/n\)，则

\[\displaystyle E[T(n)] = \frac{1}{n} \sum_{k=1}^{n} [T(k-1) + T(n-k) + O(n)]=\frac{2}{n} \cdot \sum_{k=1}^{n-1} E[T(k)] + O(n)\]

下证明 \(E[T(n)] \leqslant a \cdot n \log n\)，其中 \(a\) 是待定常数。 $\(\displaystyle E[T(n)] \leqslant \frac{2}{n} \cdot \sum_{k=1}^{n-1} E[T(k)] + cn\)\(（\)cn$ 表示分区操作耗时）

假设对于所有小于 \(n\) 的 \(k\)，都有 \(E[T(k)] \leqslant a \cdot k \log k\) ，则： $\(\displaystyle E[T(n)] \leqslant \frac{2a}{n} \cdot \sum_{k=1}^{n-1} k \log k + cn\)$ 函数 \(f(x) = x \log x\) 单调递增，所以： $\(\displaystyle \sum_{k=1}^{n-1} k \log k \leqslant \int_{1}^{n} x \log x \, dx= \frac{x^2}{2} \log x - \frac{x^2}{4}\)$ 代入上下限 \([1, n]\)得

\[\displaystyle E[T(n)] \leqslant an \log n - \frac{an}{2} + \frac{a}{2n} + cn\]

即： $\(\displaystyle E[T(n)] \le an \log n - \left( \frac{1}{2}(a - 2c) \cdot n - \frac{a}{2n} \right)\)$

取 \(a = 3c\)即可。

Proof2：指示随机变量法。

通过考察任意两个元素是否会被相互比较来计算时间复杂度。

  • 快速排序的时间复杂度主要取决于划分时的比较次数。
  • 假设数组排序后的结果是 \(z_1, z_2, \dots, z_n\)。
  • 定义指示随机变量 \(X_{i,j}\)：
    • 如果 \(z_i\) 和 \(z_j\) 在排序过程中发生了比较，那么 \(X_{i,j} = 1\)，否则 \(X_{i,j} = 0\)
  • 时间复杂度的期望是 \(\displaystyle E[\sum X_{i,j}] = \sum E[X_{i,j}]\)。
  • 考虑排序后的序列中，\(z_i\) 和 \(z_j\) 以及它们之间的所有元素，组成的集合为 \(Z_{i,j} = \{z_i, z_{i+1}, \dots, z_j\}\)，共有 \(j-i+1\) 个元素。
  • 规则 1：如果在 \(Z_{i,j}\) 中，任何一个位于 \(z_i\) 和 \(z_j\) 之间的元素被选为了界限，则 \(z_i\) 和 \(z_j\) 将被分到两个不同的子数组，它们在以后过程中永远不会被比较。
  • 规则 2：如果 \(z_i\) 或 \(z_j\) 本身被选为了 \(Z_{i,j}\) 集合中第一个基准值，那么它们一定会发生一次比较。
  • 每个元素成为第一个基准值的概率相等，为 \(1/(j-i+1)\)。
  • \[\displaystyle \text{Total Expected Comparisons} = \sum_{i=1}^{n-1} \sum_{j=i+1}^n \frac{2}{j-i+1}\]

  • 令 \(k = j-i+1\)，对每一个固定的 \(i\)，当 \(j\) 从 \(i+1\) 变到 \(n\) 时，\(k\) 从 \(2\) 变到 \(n-i+1\)，则求和式小于：\(\displaystyle \sum_{i=1}^{n} \sum_{k=2}^{n} \frac{2}{k}\)，约为 \(n \cdot 2 \cdot \ln n\)，即 \(O(n \log n)\)。

时间复杂度 原地性 稳定性
插入排序 \(O(n^2)\) 是 是
选择排序 \(O(n^2)\) 是 否
冒泡排序 \(O(n^2)\) 是 是
堆排序 \(O(n\log n)\) 是 否
归并排序 \(O(n\log n)\) 否 是
快速排序 \(O(n\log n)\) 是 否

基于比较的排序算法的最优下界是\(\Omega(n\log n)\)

对于基于比较的确定性排序算法，可以使用决策树来模拟排序过程。最差时间不小于树的深度\(D\)。记树的叶子结点为排序所对应的最终状态，叶子数为包含\(n\)个元素序列的全排列数，即\(n!\)，故\(D\geqslant \log_2n!=\Omega(n\log n)\)，即最差时间复杂度为\(\Omega(n\log n)\)

下面说明叶子结点的平均深度也为\(\Omega(n\log n)\)

假设目前的树是完全二叉树，显然成立，若不然，一定存在一个叶子结点\(x\)，其深度较小，一定存在一对叶子结点，其深度较大，将这一对叶子结点接到\(x\)下方，重复此操作直到形成完全二叉树，且叶子总深度在不断减小，故平均深度一定大于完全二叉树的情况，故得证。

下面证明，对于基于比较的随机化排序算法，其期望时间复杂度也为\(\Omega(n\log n)\)

考虑所有 \(n!\) 种初始序列排列以均匀分布形式出现。一个随机化算法可以看作是一个函数 \(A(\cdot, R)\)，其中 \(R\) 是预先生成的随机序列。如果固定随机序列 \(R\)，算法 \(A(\cdot, R)\) 将成为确定性算法。对于每一个固定的 \(R\)，算法 \(A(\cdot, R)\) 都对应一棵特定的决策树。

对于任意确定的 \(R\)：正如第一步所说，只要是确定的比较排序树，它在均匀分布 \(D\) 下的平均运行时间必然 \(\ge \Omega(n \log n)\)。

期望的累加：随机化算法的期望复杂度 \(\mathbb{E}_{R,\pi \sim D}[T(A(\pi, R))]\) 是对所有随机情况 \(R\) 的加权平均。数学表达为：\(\sum_{R} \text{Prob}(R) \times (\text{确定性算法 } A_R \text{ 在分布 } D \text{ 下的平均表现})\)。

既然每一个单独的确定性算法 \(A_R\) 的平均表现都跑不出 \(\Omega(n \log n)\) 的限制，那么它们的加权平均值也一定不低于 \(\Omega(n \log n)\)。

平均时间与期望时间的区别：平均时间指在算法固定的情况下，对于某个输入分布，任取其中的一个确定输入，计算得到正确结果的时间的平均，是对输入的随机性做平均；而期望时间则主要用于随机化算法，是对算法的随机性做平均（期望）。

姚期智极小极大原理（Yao's Minimax Principle）

在算法理论中，我们通常处理两类复杂性： 1. 随机化算法的复杂性：算法本身会抛硬币，对同一个输入，多次运行时间可能不同。 2. 确定性算法的平均复杂性：算法是固定的，但输入是随机生成的。

姚期智注意到，这两种情况可以看作一种零和博弈： * 玩家 A（算法设计者）：想要选择一个算法（可能是随机化的），使运行时间尽量短。 * 玩家 B（大自然/对手）：想要选择一种输入的分布，使算法的运行时间尽量长。

假设 \(T(A, x)\) 是算法 \(A\) 处理输入 \(x\) 的代价。 * 对于随机化算法，其代价是所有随机选择 \(R\) 的期望值：\(\mathbb{E}_R [T(A_R, x)]\)。 * 对于某种输入分布 \(D\)，确定性算法的代价是输入 \(x\) 的平均值：\(\mathbb{E}_{x \sim D} [T(A, x)]\)。

Yao's Principle 指出： $\(\max_{x} \mathbb{E}_R [T(A_R, x)] \ge \min_{A} \mathbb{E}_{x \sim D} [T(A, x)]\)$

即：随机化算法在最坏输入下的性能下界 \(\ge\) 任何确定性算法在某种特定输入分布下的平均性能下界。

  1. 构造分布 \(D\)：我们选定一个“均匀随机排列”作为输入分布（即 \(\{1, \dots, n\}\) 的 \(n!\) 种排列概率均等）。
  2. 固定算法 \(A\)：对于任何一个固定的随机数序列 \(R\)，算法 \(A(\cdot, R)\) 就退化成了一个确定性排序算法。
  3. 计算平均性能：根据决策树模型，任何确定性算法在均匀分布 \(D\) 下的平均深度（比较次数）至少是 \(\log_2(n!)\)，即 \(\Omega(n \log n)\)。
  4. 得出结论：既然对于每一个固定的 \(R\)，该算法的平均表现都逃不开 \(\Omega(n \log n)\)，那么根据姚氏原理，原始随机化算法的期望复杂度也一定逃不开这个下界。

桶排序（Bucket Sort）（期中不考）

用于整数排序。

假设待排序的序列元素的值域是\([1,U]\)，那么准备\(U\)个桶，将第\(i\)个元素放到第\(A[i]\)个桶，最后从小到大遍历桶，循环输出桶中元素计数即可。

时间复杂度\(O(n+U)\)，空间复杂度\(O(n+U)\)

基数排序（Radix Sort）（期中不考）

按照每一位进行比较，记基数为\(k\)，一般为十进制：\(k=10\)，对应最大数字的位数为\(d\)。

从最低位进行分析，从左至右，将元素按照最低位依次投入\(0\sim 9\)这十个桶，再从左至右取出，这算做一轮。

第二轮则考虑倒数第二位，若某元素在此位无数，则记为零，以此类推直到结束最高位循环。

时间复杂度为\(O((n+10)d)=O(nd)>O(n\log_kn)=\Theta(n\log n)\)