数据结构-排序

快速排序

依据轴点做划分，使得

$$max[lo,mi)\le [mi]\le min(mi,hi]$$

前缀和后缀各自递归即可。

• Insight: 相距更远的逆序对更优先被消除

一个序列有序当且仅当所有元素均为轴点。

划分 LUG

任取一个元素作为轴点，从两端交替向内移动 $lo$ 和 $hi$，将小于/大于轴点的元素归入 L/G，最后将轴点归位。

• 线性时间
• 就地
• 不稳定

空间复杂度

取决于递归深度

• 最好：$O(\log n)$
• 最坏：$O(n)$

优化：迭代化+贪心，缺一不可 思想：小区间优先被处理

归纳假设：对长度 $m<n$ 的序列，该算法所需空间不超过 $\log m$ 对于长度为 $n$ 的序列，算法执行过程分为三个阶段：

• 第一次划分后，$|Task|=2$
• 对小区间排序的过程中，$|Task|\le 1+\log (n/2)=\log n$
• 对大区间排序的过程中，此时小区间已经排序完成，$|Task|\le \log (n-1)<\log n$ 优化后可以保证空间复杂度为 $O(\log n)$

为什么要求迭代化？ 如果不迭代化，进行子任务时父任务的栈帧不会被释放，则最坏情况仍会达到 $O(n)$

时间复杂度

• 最好：每次划分接近平均

$$T(n)=2T((n-1)/2)+O(n)=O(n\log n)$$

• 最坏：每次划分不均衡

$$T(n)=T(n-1)+T(0)+O(n)=O(n^2)$$

采用随机选取、三者取中的策略来降低最坏情况的概率。

递归深度

• 好轴点：落在居中的长度为 $\lambda n$ 的区间内
• 坏轴点：落在两侧的长度共 $(1-\lambda )n$ 的区间内

任何一条递归路径上，好轴点不会超过 $d(n,\lambda )={\log }_{2/(1+\lambda )}n$ 个

由于好轴点个数和坏轴点个数之比的期望为 $\lambda /(1-\lambda )$

因此抵达 $1/\lambda \cdot d(n,\lambda )$ 层时，期望已经出现了 $d(n,\lambda )$ 个好轴点，因此期望在此之前结束递归。

• 任何一条递归路径的长度只有极小概率超过 $D(n,\lambda )=2/\lambda \cdot d(n,\lambda )$

比较次数

递推分析：

$$T(n)=(n-1)+\frac{1}{n}\cdot \sum _{k=0}^{n-1}[T(k)+T(n-k-1)]=(n-1)+\frac{2}{n}\cdot \sum _{k=0}^{n-1}T(k)$$ $$T(n)\approx 2n\ln n$$

后向分析： 对于排序后的序列 $\{a_0,\dots ,a_i,\dots ,a_j,\dots ,a_{n-1}\}$，考虑 $a_i$ 和 $a_j$ 进行过比较的概率 $Pr(i,j)$：

• 若 $k\notin [i,j]$，则 $a_k$ 早于或晚于 $a_i$ 和 $a_j$ 被转化为 pivot 与二者是否被比较没有关系。
• 若 $k\in (i,j)$，则 $a_i$ 和 $a_j$ 不会被比较。

因此 $a_i$ 和 $a_j$ 进行过比较当且仅当在 $[i,j]$ 中，$a_i$ 或 $a_j$ 最先被转化为 pivot，因此 $Pr(i,j)=\frac{2}{j-i+1}$，期望总比较次数为

$$T(n)=\sum _{j=1}^{n-1}\sum _{d=1}^{j}Pr(i,j)=\sum _{j=1}^{n-1}2(\ln j-1)\le 2n\ln n$$

对比

LGU 版实现的期望交换次数是期望比较次数的 $1/6$

DUP

若有大量相同元素（甚至全部元素相同），则递归深度退化为 $O(n)$，复杂度会退化为 $O(n^2)$ 在交替迭代 $lo$ 和 $hi$ 时，将判断当前元素是否小于等于/大于等于 pivot 改为判断当前元素是否小于/大于 pivot

• 一般情况下复杂度并未提高

遇到连续的相等元素时，$lo$ 和 $hi$ 会交替移动，最终切分点接近 $(lo+hi)/2$，避免了递归深度的退化

• 交换次数有所增加，且更不稳定

LGU

将数据划分方式从 LUG 改为 LGU

• 若当前元素小于 pivot，交换当前元素和 mi+1（G 的第一个元素）
• 若当前元素大于等于 pivot，直接 k++
• 最后将 pivot 和 mi 交换 缺点：
• 交换次数多，每遇到一个 L 中的数就需要交换一次，期望上交换次数是比较次数的 $1/2$
• 不稳定

选取第 k 大

QuickSelect

反复做 QuickPartition，若猜大了则删除后缀，若猜小了则删除前缀

期望性能： $T(n)=(n-1)+\frac{1}{n}\cdot {\sum }_{k=0}^{n-1}max\{T(k),T(n-k-1)\}$ $T(n)\le (n-1)+\frac{2}{n}\cdot {\sum }_{k=n/2}^{n-1}T(k)$ 可以验证 $T(n)<4n$

LinearSelect

linearSelect(A, n, k)：从 $n$ 个数中找到第 $k$ 小的数

$Q$ 为一个较小的值 0. 若 $n<Q$，直接进行排序并返回答案，视为 $O(1)$

1. 否则，将序列切分为 $n/Q$ 个子序列
2. 对每个子序列进行排列
3. 每个子序列得到各自的中位数
4. 将这些中位数作为一个新的序列，递归调用 linearSelect，找到中位数的中位数 $M$
5. 将 $M$ 作为 pivot，将 $A$ 划分为 L/E/G 三部分
6. 若 $k\le |L|$，第 $k$ 小在 $L$ 中，返回 linearSelect(A, |L|, k)；若 $|L|<k\le |L|+|E|$，说明 $M$ 就是第 $k$ 小；否则返回 linearSelect(A+|L|+|E|, |G|, k-|L|-|E|)

复杂度

• 对每个子序列进行排序：$O(Q^2\times n/Q)=O(Qn)$
• 收集所有子序列中位数：$O(n/Q)$
• 递归找到中位数的中位数：$T(n/Q)$
• 一次扫描，分类 L/E/G 并计数：$O(n)$
• 递归调用：$T(3n/4)$ 选取方式可以保证 $min(|L|,|G|)+|E|\ge n/4$：由图，绿/蓝+黄必然覆盖了 1/4 的数

则 $max(|L|,|G|)\le 3n/4$

因此有递推式 $T(n)=O(n)+T(n/Q)+T(3n/4)$

只需保证 $1/Q+3/4<1$ 即可保证 $T(n)=O(n)$，取 $Q=5$ 即可

希尔排序

将整个序列视作一个矩阵，逐列进行排序，然后减少列数，重复直至列数为 1，此时再做一次排序即可。

Shell 序列

$\{1,2,4,8,\dots ,2^k,\dots \}$ 最坏情况下需 $\Omega (n^2)$ 时间 最后的全排序仍需 $\Omega (n^2/4)$ 时间

邮票问题

任给两个数 $g,h$，它们的线性组合能否表示另一个数 $P$？

当 $g,h$ 互质时，它们的线性组合不能表示的最大自然数为 $(g-1)(h-1)=gh-g-h$

h-sorting & h-ordered

称一个序列为 h-ordered 当且仅当 $S[i]\le S[i+h]$

Theorem

对于任意正整数， A g-ordered sequence remains g-ordered after being h-sorted.

Theorem

一个同时为 g-ordered 和 h-ordered 的序列必然是 (mg+nh)-ordered 的

如果 $g,h$ 互质，则对于任意的元素，只有前面的 $gh-g-h$ 个元素中可能出现逆序对，它和再之前的元素间必然有序。

PS 序列

若 $g,h$ 互质，且均为 $O(d)$ 的，则可以在 $O(dn)$ 时间内完成 d-sorting

$\{2^k-1|k\in \mathbb{N}\}$

相邻两个元素互质

需要进行 $O(\log n)$ 次外层循环

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

Pratt 序列

$\{2^p\cdot 3^q|p,q\in \mathbb{N}\}$

时间复杂度为 $O(n{\log }^{2}n)$

需要过多次循环，对于接近有序的序列效率较低

Sedgewick 序列

最坏时间复杂度 $O(n^{4/3})$

平均时间复杂度 $O(n^{7/6})$