DSA - 排序

我亲爱的 OOP 只有裸考了。数据结构要复习不完了。不做习题集了。

残江残江山寂无常客，晓风晓风月心有灵犀。

快速排序

找一个轴点，也就是排序之后也就在现在这个位置的点。这样左右两边可以递归地排序。

0001 template <typename T> void Vector<T>::quickSort( Rank lo, Rank hi ) {
0002    if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
0003    Rank mi = partition( lo, hi ); //在[lo, hi)内构造轴点
0004    quickSort( lo, mi ); quickSort( mi + 1, hi ); //前缀、后缀各自递归排序
0005 } //quickSort

划分构造轴点。

LUG：

任选一个轴点，逐个检查当前元素，更小入 L，更大入 G，当 U 缩减殆尽之后把候选嵌入中间成为轴点。

0001 template <typename T> //通过调整元素位置，构造出区间[lo, hi)内的一个轴点
0002 Rank Vector<T>::partition( Rank lo, Rank hi ) { //LUG版：基本形式
0003    swap( _elem[lo], _elem[lo + rand() % ( hi - lo )] ); //任选一个元素与首元素交换
0004    T pivot = _elem[lo]; //经以上交换，等效于随机选取候选轴点
0005    while ( lo < hi ) { //从两端交替扫描，直至相遇
0006       do hi--; while ( ( lo < hi ) && ( pivot <= _elem[hi] ) ); //向左拓展后缀G
0007       if ( lo < hi ) _elem[lo] = _elem[hi]; //阻挡者归入前缀L
0008       do lo++; while ( ( lo < hi ) && ( _elem[lo] <= pivot ) ); //向右拓展前缀L
0009       if ( lo < hi ) _elem[hi] = _elem[lo]; //阻挡者归入后缀G
0010    } //assert: quit with lo == hi or hi + 1
0011    _elem[hi] = pivot; //候选轴点置于前缀、后缀之间，它便名副其实
0012    return hi; //返回轴点的秩
0013 }

双指针，线性，但是不稳定。

空间复杂度

如果轴点选择不均衡，可能出现任务划分偏侧。

Sedgewick’s Trick：维护手工栈，让划分出来的大任务先入栈后完成，小任务后入栈先完成，确保当前处理的任务不超过上一次入栈的任务的 1 / 2, 于是栈的深度是 O (logn)

时间复杂度

均衡划分能有最好情况：T (n)=2T ((n-1)/2)+O (n)=O (nlogn)；

极不均衡就是 O (n^2) 和冒泡坐一桌。

把中间 $\lambda$ 都称作好轴点，任何一条路径上，好轴点的数量不会超过：

$n(\frac{1+\lambda}{2})^2=1,d=log_{2/(1+\lambda)}n$

考查 [lo]、[(lo + hi)/2]、[hi-1]，选出居中者，作为 pivot。

设 T (n) 是期望的比较操作次数

$T(n)=(n-1)+\frac{1}{n}\sum_0^{n-1}(T(k)+T(n-k-1))$

n-1 是本层划分时，轴点必须和其他人都比较一次的必须开销，1 / n 是随机挑选轴点，求和是对左右子树。

最后算出来期望 O (nlogn)

后向分析：假设已经做好排序，得到升序序列，讨论 P (i,j) 为 ai 和 aj 发生比较的概率。P (i,j) 的期望就是他自己，因为每一对要么比 1 次要么比 0 次。

如果 ai-aj 中间有个元素 ak 被率先选作轴点，那么 ai-aj 就被分到不同的子树去就没可能比较。所以发生比较的充要条件是 ai 或 aj 在 ai-aj 的所有元素中第一个被选成轴点，概率 2/j-i+1

代入，内层调和级数求和是 logn，外层对 logn 求和是 nlogn

各种排序算法：

快速选取

借用快排的划分，比较 k 和当前取到的轴点 mid，k 在 mid 左侧说明继续在左侧找，在 mid 右侧在右边找，直到恰好分到。

0001 template <typename T> Rank quickSelect( const T* A, Rank n, Rank k ) { //基于快速划分的k选取算法
0002    Vector<Rank> R(n); for ( Rank i = 0; i < n; i++ ) R.insert(i); //使用索引向量，保持原序列的次序
0003    for ( Rank lo = 0, hi = n; ; ) { //反复做quickParititon
0004       swap( R[lo], R[lo + rand()%(hi-lo)] ); T pivot = A[R[lo]]; Rank mi = lo; //大胆猜测
0005       for ( Rank i = lo+1; i < hi; i++ ) //LGU版partition算法
0006          if ( A[R[i]] < pivot )
0007             swap( R[++mi], R[i] );
0008       swap( R[lo], R[mi] ); //[0,mi) < [mi] <= (mi, n)
0009       if ( k < mi ) hi = mi; //猜大了，则剪除后缀
0010       else if ( k == mi ) return R[mi]; //或早或迟，总能猜中
0011       else lo = mi + 1; //猜小了，则剪除前缀
0012    } //for
0013 } //quickSelect

改进：中位数的中位数算法

将 n 个元素分成 Q 组，对 n / Q 个小数组排序找每个小数组中位数，收集这些中位数再递归调用算法自身找出他们的中位数，用作轴点

T (n)=O (n)+T (n/Q)+T (max (|L|,|Q|))，分别代表找 n/Q 个中位数的复杂度，在所有中位数中找中位数的复杂度，递归划分的复杂度。

中间的红点 m 是局部中位数，M 是中位数的中位数，大于等于 M 的那些中位数连带其上的 GE 区块至少有 n / 4，那么严格小于的就是至多 0.75n；同理看左下角，严格大于 M 至多 0.75n，max<=0.75n，于是取 Q = 5 由大师定理 T 是线性的。

希尔排序

0001 template <typename T> void Vector<T>::shellSort( Rank lo, Rank hi ) {
0002    for ( Rank d = 0x7FFFFFFF; 0 < d; d >>= 1 ) //PS Sequence: { 1, 3, 7, 15, 31, ... }
0003       for ( Rank j = lo + d; j < hi; j++ ) { //for each j in [lo+d, hi)
0004          T x = _elem[j]; Rank i = j; //within the prefix of the subsequence of [j]
0005          while ( ( lo + d <= i ) && ( x < _elem[i - d] ) ) //find the appropriate
0006             _elem[i] = _elem[i - d], i -= d; //predecessor [i]
0007          _elem[i] = x; //where to insert [j]
0008       }
0009 } //shellSort

对独立的一列做插入排序。宏观上意味着相距 d 的元素已经有序。

希尔步长序列：2 的次幂。

因为步长序列各项不互素。

邮票问题：g 和 h 不互素，最大不能线性表出的数值是 gh-g-h

K- 定理：一个序列已经 g- 有序了再做 h- 排序一定还是 g- 有序的

那么做完 g- 排序和 h- 排序之后，相距超过 gh-g-h 的元素一定已经有正确相对顺序。

PS 序列：2 的幂次 - 1, 实现 O (n^1.5)