排序算法

发表于 分类于

此前我们涉及了诸多排序算法，针对向量和列表的起泡排序、归并排序以及选择排序等算法，基于散列的桶排序算法，借助堆的性质的就地堆排序算法。在此外，排序算法还有快速排序算法，希尔排序算法，其构思和技巧各具特色，在不同应用中的效率也各有千秋。

快速排序

与归并排序一样，快速排序也是分治策略的典型应用，但二者有本质的区别，归并排序的计算量主要消耗于有序向量的归并操作，而子向量的划分却几乎不费时间。快速排序相反，可以在$O(1)$时间内由子问题的解得到原问题的解，但为了将原问题划分为两个子问题却需要$O(n)$时间。

轴点

考查任一向量区间$S[lo,hi)$。对于任何$lo \leq mi<hi$,以元素S[mi]为界限，都可分割出前、后两个子向量$S[lo,mi)$和$S(mi,hi)$。若$S[lo,mi)$中的元素均不大于$S[mi]$,且$S(mi,hi)$中的元素均不小于$S[mi]$，则元素$S[mi]$称作向量$S$的一个轴点。

以轴点$S[mi]$为界，前后向量的排序各自可独立进行，一旦前后向量各自完成排序，则可立即在常数时间内得到整个向量的排序结果。

1
2
3
4
5
6
7
template <typename T> //向量快速排序
void Vector<T>::quickSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
   if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
   Rank mi = partition ( lo, hi - 1 ); //在[lo, hi - 1]内构造轴点
   quickSort ( lo, mi ); //对前缀递归排序
   quickSort ( mi + 1, hi ); //对后缀递归排序
}

在原始序列中轴点未必存在，任何一个元素作为轴点的必要条件是在初始向量和排序后向量中的秩应相等。只要所有元素都是错位的，则任何元素都不可能是轴点。但是可通过交换使任一元素转换为轴点。

任取一候选者，前缀$L$小于等于候选者，初始时为空，后缀$G$大于等于候选者，初始为空，中间区域待确定，初始为全集。交替向内移动$lo$和$hi$，逐个检查当前元素，若更小/大，则转移归入$L/G$。当$lo=hi$时，只需将候选者嵌入$L$、$G$之间，即为轴点。整个过程中，每个元素最多移动一次(候选者两次)，累计$O(n)$时间，$O(1)$辅助空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename T> //轴点构造算法：通过调整元素位置构造区间[lo, hi]的轴点，并返回其秩
Rank Vector<T>::partition ( Rank lo, Rank hi ) { //版本B：可优化处理多个关键码雷同的退化情况
   swap ( _elem[lo], _elem[lo + rand() % ( hi - lo + 1 ) ] ); //任选一个元素与首元素交换
   T pivot = _elem[lo]; //以首元素为候选轴点——经以上交换，等效于随机选取
   while ( lo < hi ) { //从向量的两端交替地向中间扫描
      while ( lo < hi )
         if ( pivot < _elem[hi] ) //在大于pivot的前提下
            hi--; //向左拓展右端子向量
         else //直至遇到不大于pivot者
            { _elem[lo++] = _elem[hi]; break; } //将其归入左端子向量
      while ( lo < hi )
         if ( _elem[lo] < pivot ) //在小于pivot的前提下
            lo++; //向右拓展左端子向量
         else //直至遇到不小于pivot者
            { _elem[hi--] = _elem[lo]; break; } //将其归入右端子向量
   } //assert: lo == hi
   _elem[lo] = pivot; //将备份的轴点记录置于前、后子向量之间
   return lo; //返回轴点的秩
}

性能分析

为不稳定算法，$lo/hi$的移动方向相反，左/右侧的大/小重复元素可能前后颠倒。同时为就地算法，只需$O(1)$附加空间。递归实例在最坏情况下需要$\Omega(n)$空间。

partition算法可在线性时间内将原向量分解为两个相互独立、总体规模保持线性的子向量排序问题，根据轴点的性质，由排序后的向量可在常数时间内得到整个有序向量。分治策略高效实现的两个必要条件满足，即子问题划分的高效性和子问题相互之间的独立性，但是子任务规模相近在此处却无法保证。
partition算法划分所得子序列长度与划分的具体过程无关，完全取决于入口处所选的轴点。若在最终有序向量中该候选元素的秩为$r$，则子向量的规模必然为$r$和$n-r-1$。

最好情况：每次划分都接近平均，轴点总是接近中央。

$\displaystyle T(n)=2T(\frac{n-1}{2})+O(n)=O(nlogn)$

最坏情况：每次划分都极不均衡

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

可以通过随即选取一个候选轴点，或者从待排序向量中任取三个元素，将其数值居中者作为候选者，来降低最坏情况出现的概率，但是无法杜绝最坏情况的概率。

以下分析平均效率

准居中：pivot的秩落在宽度为$\lambda n$的居中区间，每以递归路径上，至多出现$log_{\frac{2}{1+\lambda} n}$ 个准居中的轴点。

每递归一层，都有$\lambda|(1-\lambda)$的概率准居中|准侧偏

深入$\displaystyle \frac{1}{\lambda}log_{\frac{2}{1+\lambda} n}$ 层后，即可期望出现$\displaystyle log_{\frac{2}{1+\lambda}} n$次居中，且有极高的概率出现，因此有极高的概率递归深度不超过$\displaystyle \frac{1}{\lambda}log_{\frac{2}{1+\lambda} n}=3log_{3/2} n$

假设待排序的元素都符合独立均匀分布，partition算法经过$n-1$次比较和$n+1$次移动之后，对规模为$n$的向量划分结果无非两种可能，划分所分左侧子序列的长度分别是$0,1,..,n-1$次，分别决定于所取元素在候选节点在最终有序序列中的秩。

$\displaystyle T(n)=(n+1)+\frac{1}{n} \sum_{k=0}^{n-1}[T(k)+T(n-k-1)]$

$\displaystyle =(n+1)+\frac{2}{n} \sum_{k=0}^{n-1}T(k)$

等式两侧同时乘以$n$，则有：

$nT(n)=n(n+1)+2\sum_{k=0}^{n-1}T(k)$

$(n-1)T(n-1)=(n-1)+2\sum_{k=0}^{n-2}T(k)$

两式相减，得$nT(n)-(n-1)T(n-1)=2n+2T(n-1)$

$nT(n)=2n+(n+1)T(n-1)$

两边同时除以$n(n+1)$,得

$T(n)/(n+1)=2/(n+1)+T(n-1)/n$

$=2/(n+1)+2/n+T(n-2)/(n-1)$

$=2/(n+1)+2/n+2/(n-1)+…2/2+T(0)/1$

$<2lnn$

$T(n) \approx 2nlnn=(2ln2)nlogn \approx 1.386logn=O(nlogn)$

退化情况

考查所有元素均退化的情况，主循环内部前一子循环的条件pivot<=_elem[hi] 形同虚设，此时，划分的结果必然是以最左端为轴点，原向量划分为极不对称的两个子向量，这一最坏情况还可能持续发生，从而使整个算法过程等效地退化为线性递归，递归深度为$O(n)$，导致总体运行时间高达$O(n^2)$。

可以再每次深入递归时统一核验，若确为退化情况，则无需递归而直接返回，但在重复元素不多时，如此会增加额外的计算量，总体权衡后得不偿失。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T> //轴点构造算法：通过调整元素位置构造区间[lo, hi]的轴点，并返回其秩
Rank Vector<T>::partition ( Rank lo, Rank hi ) { //版本B1：版本B的等价形式，可直接转至与版本A等价的版本A1
   swap ( _elem[lo], _elem[lo + rand() % ( hi-lo+1 ) ] ); //任选一个元素与首元素交换
   T pivot = _elem[lo]; //以首元素为候选轴点——经以上交换，等效于随机选取
   while ( lo < hi ) { //从向量的两端交替地向中间扫描
      while ( ( lo < hi ) && ( pivot < _elem[hi] ) ) //在大于pivot的前提下
         hi--; //向左拓展右端子向量
      if ( lo < hi ) _elem[lo++] = _elem[hi]; //不大xia于pivot者归入左端子向量
      while ( ( lo < hi ) && ( _elem[lo] < pivot ) ) //在小于pivot的前提下
         lo++; //向右拓展左端子向量
      if ( lo < hi ) _elem[hi--] = _elem[lo]; //不小于pivot者归入右端子向量
   } //assert: lo == hi
   _elem[lo] = pivot; //将备份的轴点记录置于前、后子向量之间
   return lo; //返回轴点的秩
}

与版本A比较，版本B主要是调整了两个内循环的终止条件。将原条件pivot<=elem[hi]更改pivot<elem[hi],一旦遇到重复元素，右端子向量随即终止拓展，并将右端重复元素移至左端，lo和hi会交替移动，二者移动距离大致相当。但是以上改进需做更多的交换操作，倾向于交换重复元素，所以重复元素在原输入向量中的相对次序更难保持。

构造轴点的另一快捷思路：

始终将整个向量划分为四个区间，$v[lo],L=v(lo,mi],G=v(mi,k],u=v[k,hi]$

其中$v[lo]$为候选轴点，$L/G$中的元素均不大/不小于$v[lo]$，$U$中元素大小未知。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename T> //轴点构造算法：通过调整元素位置构造区间[lo, hi]的轴点，并返回其秩
Rank Vector<T>::partition ( Rank lo, Rank hi ) { //版本C
   swap ( _elem[lo], _elem[lo + rand() % ( hi - lo + 1 ) ] ); //任选一个元素与首元素交换
   T pivot = _elem[lo]; //以首元素为候选轴点——经以上交换，等效于随机选取
   int mi = lo;
   //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   //   [ ---- < [lo] ----- ] [ ----- [lo] <= --- ] [ ----- unknown ----- ]
   // X x . . . . . . . . . x . . . . . . . . . . . x . . . . . . . . . . x
   // |                     |                       |                     |
   // lo (pivot)            mi                      k                     hi
   //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   for ( int k = lo + 1; k <= hi; k++ ) //自左向右扫描
      if ( _elem[k] < pivot ) //若当前元素_elem[k]小于pivot，则
         swap ( _elem[++mi], _elem[k] ); //将_elem[k]交换至原mi之后，使L子序列向右扩展
   //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   //   [ --------- < [lo] ---------- ] [ ----------- [lo] <= ----------- ]
   // X x . . . . . . . . . . . . . . x . . . . . . . . . . . . . . . . . x
   // |                               |                                   |
   // lo                              mi                                  hi
   //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   swap ( _elem[lo], _elem[mi] ); //候选轴点归位
   return mi; //返回轴点的秩
}

初始时取$k-1=mi=lo$,$L$和$G$均为空，此后随着$k$不断递增，逐一检查元素$v[k]$，并根据$v[k]$相对于候选轴点的大小，相应地扩展区间$L$或区间$G$，同时压缩区间$U$。最终，当$k-1=hi$时，$U$中不含任何元素，于是只需将候选轴点放至$V[mi]$，即成为真正的轴点。

基于以上实现的快速排序算法不稳定，子向量L和R都是向右侧延伸，新元素都是插至向量的末尾。除此以外，子向量$L$不会有任何修改，故其中所有元素之间的相对次序必然与原向量一致。然而，在子向量$L$的每次生长之前，子向量$R$都需要相应地向前滚动一个单元，故可能造成雷同元素之间相同次序的紊乱。在元素大量甚至完全重复的情况下该算法虽不致出错，但划分所得的子向量的规模相差悬殊，几乎退化成起泡排序算法，整体运行时间将增加到$O(n^2)$。

选取与中位数

k选取

在任意一组可比较大小的元素中，如何从小到大找出其中次序为$k$者？亦即在这组元素的非降排序序列$S$中找出$S[k]$。

中位数

长度为$n$的有序序列中，元素$S[n/2]$称作中位数(数值上可能有重复)。在任意一组可比较大小的元素中，如何找到中位数？

中位数是$k$选取问题的一个特例，也是其中难度最大者。由于中位数可将原数据集划分为大小明确、规模相仿且彼此独立的两个子集，故能否高效地确定中位数将直接关系到分治策略可否高效实现。

蛮力算法

由中位数的定义，可直接得到查找中位数的算法如下：对所有元素排序，将其转化为有序序列S，则$S[n/2]$即为所要找的中位数。对无序向量的排序在最坏情况下需要$\Omega(nlogn)$时间，故基于该算法的任何分治算法，时间复杂度都不会低于$T(n)=nlogn+2T(n/2)=O(nlog^2n)$

不妨考虑中位数问题的一个简化版，在任一无序向量A中，若有一半元素的数值同为$m$,则将$m$称为A的众数。那么，任给无序向量，如何快速判断其中是否存在众数，并在存在时将其找出？

1
2
3
4
template <typename T> bool majority ( Vector<T> A, T& maj ) { //众数查找算法：T可比较可判等
   maj = majEleCandidate ( A ); //必要性：选出候选者maj
   return majEleCheck ( A, maj ); //充分性：验证maj是否的确当选
}

通过调用majEleCandidate() ,从向量A中找到中位数maj，并将其作为众数唯一候选者。再调用majEleCheck()

在线性时间内扫描一遍向量，从而最终判断向量A的众数是否的确存在。

1
2
3
4
5
6
template <typename T> bool majEleCheck ( Vector<T> A, T maj ) { //验证候选者是否确为众数
   int occurrence = 0; //maj在A[]中出现的次数
   for ( int i = 0; i < A.size(); i++ ) //逐一遍历A[]的各个元素
      if ( A[i] == maj ) occurrence++; //每遇到一次maj，均更新计数器
   return 2 * occurrence > A.size(); //根据最终的计数值，即可判断是否的确当选
}

设$P$为向量A中长度为$2m$的前缀，若元素$x$在P中恰好出现$m$次，则$A$有众数当且仅当后缀$A-P$有众数，同时$A-P$的众数就是$A$的众数。

若$A$的众数就是$x$,则在剪除前缀$P$之后，$x$与非众数均减少相同的数目，二者数目的差距在后缀$A-P$中保持不变。反过来，若$A-P$的众数不为$x$，则二者数目的差距在后缀$A-P$中也不会缩小。

按照以上减而治之策略，可唯一确定众数的候选者。

1
2
3
4
5
6
7
8
9
10
template <typename T> T majEleCandidate ( Vector<T> A ) { //选出具备必要条件的众数候选者
   T maj; //众数候选者
// 线性扫描：借助计数器c，记录maj与其它元素的数量差额
   for ( int c = 0, i = 0; i < A.size(); i++ )
      if ( 0 == c ) { //每当c归零，都意味着此时的前缀P可以剪除
         maj = A[i]; c = 1; //众数候选者改为新的当前元素
      } else //否则
         maj == A[i] ? c++ : c--; //相应地更新差额计数器
   return maj; //至此，原向量的众数若存在，则只能是maj —— 尽管反之不然
}

其中，变量maj始终为当前前缀中出现次数不少于一半的某个元素，c始终记录该元素与其他元素的数目之差。一旦c归零，则意味着在当前向量找到了一个可以减除的前缀$P$。在剪除该前缀后，问题范围将响应地缩小至$A-P$。此后，只需将maj重新初始化为$A-P$的首元素，并令c=1,即可继续重复上述迭代过程。

对于向量的每个秩，该算法迭代且仅迭代一步。故其运行时间，应线性正比于向量规模。

该候选者未必是众数，但也未必是原向量中出现最频繁者。该算法采取简而治之的策略，原向量等效地切分为若干区段，各区段首元素至少在其中占一半的比例。因此，最后返回的maj，实际上只是最后一个区段的准众数，未必就是整个向量的准众数。

若众数的定义修改为众数应严格地不少于其他元素，则需要对之前算法进行一定改进。

当向量规模为奇数时，准众数必然就是众数，当n为偶数时，针对准众数的查找的一种简明的调整方法是：首先任选一个元素(比如末元素)，并在$O(n)$时间内甄别其是否为准众数。不妨设该元素不是准众数，于是只需将其忽略(原向量的有效长度降低至$n-1$，为奇数)，即可将在原向量中查找众数的问题转化为在$n-1$的向量中查找众数的问题。

讨论中位数问题的另一简化版本，任给有序向量$S_1$和$S_2$，如何找出归并后有序向量的中位数

蛮力版

1
2
3
4
5
6
7
8
9
10
11
12
13
// 中位数算法蛮力版：效率低，仅适用于max(n1, n2)较小的情况
template <typename T> //子向量S1[lo1, lo1 + n1)和S2[lo2, lo2 + n2)分别有序，数据项可能重复
T trivialMedian ( Vector<T>& S1, int lo1, int n1, Vector<T>& S2, int lo2, int n2 ) {
   int hi1 = lo1 + n1, hi2 = lo2 + n2;
   Vector<T> S; //将两个有序子向量归并为一个有序向量
   while ( ( lo1 < hi1 ) && ( lo2 < hi2 ) ) {
      while ( ( lo1 < hi1 ) && S1[lo1] <= S2[lo2] ) S.insert ( S1[lo1 ++] );
      while ( ( lo2 < hi2 ) && S2[lo2] <= S1[lo1] ) S.insert ( S2[lo2 ++] );
   }
   while ( lo1 < hi1 ) S.insert ( S1[lo1 ++] );
   while ( lo2 < hi2 ) S.insert ( S1[lo2 ++] ); /*DSA*/print ( S );
   return S[ ( n1 + n2 ) / 2]; //直接返回归并向量的中位数
}

若调用蛮力算法将二者归并，则需花费$O(n_1+n_2)$时间。

实际上，上述算法只需$O((n_1+n_2)/2)$步即可终止。计算的目标是归并之后向量的中位数，并不意味着一定要显式地完成合并。实际上就此计算任务而言，只需设置一个计数器，而不必真地引入并维护一个向量结构。具体地，依然可以沿用原算法的主体流程，向量$S$只是假想式地存在。无需真正地将子向量中地元素转移至S中，只需动态地记录这一向量地规模：每当有一个元素假想式地归入其中，则计数器相应地递增。一旦计数器抵达$\lfloor (n_1+n_2)/2$,即可忽略后续元素并立即假想地归入其中，则计数器相应地递增。

减而治之

假设两子向量等长，长度均为$n$

简而治之的原理为，两子向量归并后所得的向量$S$长度为$2n$，则中位数对应的秩为$\lfloor 2n/2 \rfloor=n$，即存在$n$个元素不大于中位数，$n-1$个元素不小于中位数。若$m_1<m_2$,则在$S_2$中存在$\lceil n/2 \rceil$个数大于$m_2$，假设其中一数为$m$，可能不小于$m$的数的个数最大为$\lfloor n/2 \rfloor+\lceil n/2 \rceil -1=n-1$ ,即$m$的后继个数和在$S_2$中可能大于$m$的数的个数。因为$m$在$m_2$右侧,所以后继个数必然小于$\lfloor n/2 \rfloor$ 个，所以必然不是$S$的中位数，或者与$m_1$或$m_2$同为$S$的中位数。

同时，在$S_1$和$ S_2$减去的不小于中位数的数和不大于中位数的个数相等，所以在减去前后两个子向量所对应的中位数不变。

1
2
3
4
5
6
7
8
9
10
11
template <typename T> //序列S1[lo1, lo1 + n)和S2[lo2, lo2 + n)分别有序，n > 0，数据项可能重复
T median ( Vector<T>& S1, int lo1, Vector<T>& S2, int lo2, int n ) { //中位数算法（高效版）
   if ( n < 3 ) return trivialMedian ( S1, lo1, n, S2, lo2, n ); //递归基
   int mi1 = lo1 + n / 2, mi2 = lo2 + ( n - 1 ) / 2; //长度（接近）减半
   if ( S1[mi1] < S2[mi2] )
      return median ( S1, mi1, S2, lo2, n + lo1 - mi1 ); //取S1右半、S2左半
   else if ( S1[mi1] > S2[mi2] )
      return median ( S1, lo1, S2, mi2, n + lo2 - mi2 ); //取S1左半、S2右半
   else
      return S1[mi1];
}

推广至一般情况，则

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
template <typename T> //向量S1[lo1, lo1 + n1)和S2[lo2, lo2 + n2)分别有序，数据项可能重复
T median ( Vector<T>& S1, int lo1, int n1, Vector<T>& S2, int lo2, int n2 ) { //中位数算法
   if ( n1 > n2 ) return median ( S2, lo2, n2, S1, lo1, n1 ); //确保n1 <= n2
   if ( n2 < 6 ) //递归基：1 <= n1 <= n2 <= 5
      return trivialMedian ( S1, lo1, n1, S2, lo2, n2 );
   ///////////////////////////////////////////////////////////////////////
   //                lo1            lo1 + n1/2      lo1 + n1 - 1
   //                 |                 |                 |
   //                 X >>>>>>>>>>>>>>> X >>>>>>>>>>>>>>> X
   // Y .. trimmed .. Y >>>>>>>>>>>>>>> Y >>>>>>>>>>>>>>> Y .. trimmed .. Y
   // |               |                 |                 |               |
   // lo2     lo2 + (n2-n1)/2       lo2 + n2/2     lo2 + (n2+n1)/2    lo2 + n2 -1
   ///////////////////////////////////////////////////////////////////////
   if ( 2 * n1 < n2 ) //若两个向量的长度相差悬殊，则长者（S2）的两翼可直接截除
      return median ( S1, lo1, n1, S2, lo2 + ( n2 - n1 - 1 ) / 2, n1 + 2 - ( n2 - n1 ) % 2 );
   ///////////////////////////////////////////////////////////////////////
   //    lo1                  lo1 + n1/2              lo1 + n1 - 1
   //     |                       |                       |
   //     X >>>>>>>>>>>>>>>>>>>>> X >>>>>>>>>>>>>>>>>>>>> X
   //                             |
   //                            m1
   ///////////////////////////////////////////////////////////////////////
   //                            mi2b
   //                             |
   // lo2 + n2 - 1         lo2 + n2 - 1 - n1/2
   //     |                       |
   //     Y <<<<<<<<<<<<<<<<<<<<< Y ...
   //                                .
   //                               .
   //                              .
   //                             .
   //                            .
   //                           .
   //                          .
   //                         ... Y <<<<<<<<<<<<<<<<<<<<< Y
   //                             |                       |
   //                       lo2 + (n1-1)/2               lo2
   //                             |
   //                            mi2a
   ///////////////////////////////////////////////////////////////////////
   int mi1  = lo1 + n1 / 2;
   int mi2a = lo2 + ( n1 - 1 ) / 2;
   int mi2b = lo2 + n2 - 1 - n1 / 2;
   if ( S1[mi1] > S2[mi2b] ) //取S1左半、S2右半
      return median ( S1, lo1, n1 / 2 + 1, S2, mi2a, n2 - ( n1 - 1 ) / 2 );
   else if ( S1[mi1] < S2[mi2a] ) //取S1右半、S2左半
      return median ( S1, mi1, ( n1 + 1 ) / 2, S2, lo2, n2 - n1 / 2 );
   else //S1保留，S2左右同时缩短
      return median ( S1, lo1, n1, S2, mi2a, n2 - ( n1 - 1 ) / 2 * 2 );
}

该算法首先比较$n_1$和$n_2$的大小，并在必要时交换两个子向量，从而保证有$n_1<n_2$。

若两个向量相差悬殊，则可对称地适当截短长者的两翼，以保证有：

$n_1\leq n_2 \leq 2n_1$

因为$S_2$两翼截除的长度相等，所以此后$S_1 \cup S_2$的中位数，依然是$S_1\cup S_2$的中位数。

这里采用了简而治之的策略，可使问题规模按照几何级数递减，故总体复杂度应为$O(log(min(n_1,n_2)))$ 。无论是交换两个向量，还是截短$S_2$,都只需常数时间。因此实质的计算，只是针对长度均同阶于$min(n_1,n_2)$的一对向量计算中位数。此后每做一次比较，即可将问题的规模缩减至原来的一半。因此，问题的规模将以1/2为比例按几何级数的速度递减，直至平凡的递归基。整个算法的递归深度不超过$log_2{min(n_1,n_2)}$,总体时间复杂度为$O(log(min(n_1,n_2)))$。

若输入的有序序列$S_1$和$S_2$以列表的形式实现而不是向量，则在读取每个元素之前都要沿着列表进行计数查找。为保证$|S_1|<|S_2|$而交换两个序列，依然只需$ O(1)$时间，然而序列$S_2$两翼的截短则大致需要$O(n_2-n_1)$时间。而更重要的是，在此后的递归过程中，每一次为将问题规模缩减一半，都必须花费线性的时间，总体需要$O(n_1+n_2)$时间，这一效率减低到和蛮力算法相同。

为median()算法添加整型输入参数$k$，实现在$S_1\cup S_2$选取第$k$个元素的功能

记$n_1=|S_1|$和$n_2=|S_2|$,不失一般性的，设$n_1\leq n_2$

不妨设$2k \leq n_1+n_2$,否则，可以颠倒比较器的方向，原问题转化为在$S_1 \cup S_2$中选取第$n_1+n_2-k$个元素，与以下方法同理。

若$k\leq n_1=min(n_1,n_2)$,则只需令：

$S_1’=S_1[0,k)$

$S_2’=S_2[0,k)$

于是原问题即转化为计算$S_1’\cup S_2’$的中位数。

否则，若$n_1<k<n_2$,则可令

$S_1’=S_1[0,k)$

$S_2’=S_2[0,k)$

于是原问题即转化为计算$S_1’\cup S_2’$的中位数。

可见，无论如何，针对$S_1 \cup S_2$的$k$选取问题总是可在常数时间内转化为中位数问题，并调用相关的算法。

一般性的选取问题中，蛮力算法效率之所以低下是因为一组元素中第$k$大元素包含的信息量远远小于经过全排序后所得到的整个有序序列。花费足以得到全排序的计算成本，却仅得到了少量的局部信息。

堆选取

基于堆结构的选取算法大致有以下几种：

首先花费$O(n)$时间将全体元素组织为一个小顶堆，然后经过$k$次delMin()操作，则得到位序为k的元素，这一算法的时间为：

$O(n)+kO(logn)=O(n+klogn)$

另一算法为，任取k个元素，并在$O(k)$时间内组织为一个大顶堆，然后将剩余n-k个元素插入其中，每插入一个，随即删除堆顶，以使堆的规模恢复为k,待所有元素处理完毕后，堆顶即为目标元素。该算法的运行时间为：

$O(k)+2(n-k)O(logk)=O(k+2(n-k)logk)$

最后一种方法为，分别构建一个规模为$n-k$ 的小顶堆G和$k$的大顶堆H。接下来，反复比较它们的堆顶g和h，只要g小于h，则将二者交换，并重新调整为两个堆。如此，G的堆顶G将持续增大，H的堆顶将持续减小。当$g\geq h$时，h即为所要找的元素。这一算法的运行时间为：

$O(n-k)+O(k)+min(k,n-k)2log((O(log k+log(n-k))))$

在目标元素的秩很小或很大的时候($|n/2-k| \approx n/2$)，以上算法的性能都还不错。比如$k=0$时，上述两算法均只需线性时间，当$k \approx n/2$，以上算法的复杂度均退化为蛮力算法的$O(nlogn)$。

快速划分

选取问题所查找的位序$k$,就是其在对应的有序序列中的秩，就这一性质而言，与轴点颇为相似。可反复应用这一点，逐步逼近目标$k$。

首先，调用partition()构造向量$A[i]=x$，若$i=k$，则该轴点恰好就是待选取的目标元素，即可直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T> void quickSelect ( Vector<T> & A, Rank k ) { //基于快速划分的k选取算法
   for ( Rank lo = 0, hi = A.size() - 1; lo < hi; ) {
      Rank i = lo, j = hi; T pivot = A[lo];
      while ( i < j ) { //O(hi - lo + 1) = O(n)
         while ( ( i < j ) && ( pivot <= A[j] ) ) j--; A[i] = A[j];
         while ( ( i < j ) && ( A[i] <= pivot ) ) i++; A[j] = A[i];
      } //assert: i == j
      A[i] = pivot;
      if ( k <= i ) hi = i - 1;
      if ( i <= k ) lo = i + 1;
   } //A[k] is now a pivot
}

若$i$不等于$k$，则无非两种情况。

  • $k<i$,则选取的目标元素不可能来自处于$x$右侧、不小于$x$的子向量，此时不妨将该子向量剪除，然后递归地在剩余区间做k选取
  • 若$i>k$,则选取的目标元素不可能来自处于$x$左侧、不大于$x$的子向量中，同样可以将子向量剪除，然后递归地在剩余区间做$k-i$选取。

该算法流程与轴点构造算法类似，每经过一步主迭代，都会构造出一个轴点$A[i]$，然后$lo$和$hi$将彼此靠拢，查找范围将收缩至$A[i]$的某一侧。当轴点的秩$k$恰好为$k$时，算法随即终止。尽管内循环仅需$O(hi-lo+1)$时间，但是在最坏情况下需执行$\Omega(n)$次，总体运行时间为$O(n^2)$。平均时间复杂度为$O(n)$。

$T(n)=(n+1)+\frac{1}{n} \sum_{k=0}^{n} T(max(k,n-k)) =O(n)$

k选取算法

$k$选取算法的主要流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
select(A,k)
输入：规模为n的无序序列A,秩k>=0
输出：A所对应的有序序列中秩为k的元素
{
      0)if(n=|A|<Q) return trivialSelect(A,k);
      1)将A均匀地划分为n/Q个子序列，各含Q个元素
      2)各子序列分别排序，计算中位数，并将这些中位数组成一个序列
      3)通过递归调用select()，计算中位数序列的中位数，记作M
      4)根据其相对于M的大小，将A中元素分为三个子集：L(小于)M(等于)和G(大于)
      5)if(|L|>k) return select(L,k);
      else if (|L|+|E|>=K) return M;
      else return select(G,k-|L|-|E|);
}

将以上算法运行时间记作$T(n)$，则

  • 第0步：$O(1)=O(QlogQ)$
  • 第1步：$O(n)$ 子序列划分
  • 第2步：$O(n)=Q^2n/Q$ 子序列各自排序，并找到中位数
  • 第3步：$T(n/Q)$ 从$n/Q$个中位数中递归地找到全局中位数
  • 第4步：$O(n)$,划分子集L/E/G，并分别计数
  • 第5步：$T(3n/4)$

复杂度

$T(n)=O(n)+T(n/Q)+T(3n/4)$

为了使解为线性函数，只需保证：

$n/Q+3n/4<n$

若取$Q=5$,则存在常数$c$，使得

$T(n)=cn+T(n/5)+T(3n/4)$

$T(n)=O(20cn)=O(n)$

希尔排序

希尔排序将整个序列视为一个矩阵，逐列各自排序。

递减增量

由粗到细：重新排列矩阵，使其更窄，再次逐列排序

逐步求精：如此往复，直至矩阵为一列

若原一维向量宽度为$A[0,n)$，则对于任一固定的矩阵宽度$w$,$A$和$B$中元素总有一一对应关系：$B[i] [j]=A[iw+j]$,从秩的角度来看，矩阵$B$的各列依次对应于关于宽度$w$的一个同余类。不妨假设$w$整除$n$，则矩阵宽度$w$自上而下对应于$A$中以$w$为间隔的$n/w$个元素，因此，矩阵的宽度$w$亦称作增量。

希尔排序的流程如下：

1
2
3
4
5
6
7
8
9
10
11
Shellsort(A,n)
输入：规模为n的无序向量A
输出：A对应的有序向量
{
   取一个递增的增量序列：H={W1=1,W2,23,..,2K,..}
   设置k=max{i|Wi<n},即Wk为增量中小于n的最后一项
   for(t=k;t>0;t--){
       将向量A视为Wt为宽度的矩阵Bt
       对Bt的每一列分别排序，Bt[i]，i=0,1,..,Wt-1
   }
}

其中各列内部排序如何实现？

必须采用输入敏感的算法，以保证有序性持续改善，且总体成本足够低廉。比如，插入排序，更多地取决于输入序列所含逆序对的总数。

希尔排序的总体效率取决于具体使用何种步长序列

主要考查和评测

  • 比较操作、移动操作的次数
  • 收敛的速度，或者反过来，迭代的轮数

希尔序列

邮资问题

考查以下问题：

假设在某个国家，邮局仅发行面值为4分和13分的两种邮票，那么

  1. 可否用这两种邮票组合出对应的50分邮资
  2. 可否用这两种邮票组合出对应的35分邮资

线性组合

用数论的语言，以上问题可描述为：$4m+13n=35$是否存在自然数解？

对于任意自然数$g$和$h$,只要$m$和$n$也是自然数，则$f=mg+nh$都称作$g$和$h$的一个线性组合，我们称不可由$g$和$h$组合出来的最大自然数记作$x(g,h)$

如果$g$和$h$互素，则必有：

$x(g,h)=(g-1)(h-1)-1=gh-g-h$

$g=4$和$h=13$互素，故有$x(4,13)=35$，$35$恰好为无法由$4$和$13$组成的最大自然数。

h有序和h排序

在向量$S[0,n)$中，若$S[i]<=S[i+h]$对于任何$0\leq i<n-h$成立，则称该向量$h$有序，也就是说，其中相距$h$个单元的每队元素之间均有序。

考查希尔排序中对应于任一增量$h$的迭代，等同于在原向量之间以$h$间隔排序，故这一过程称为$h$排序，经$h$排序之后的向量必然$h$有序。

已经$g$有序的向量，再经过$h$排序后，依然保持$g$有序。考查$(g,h)$有序的任一向量，借助有序性的传递律可知，相距$g+h$的任何一对元素必然有序，故$S$必然$g+h$有序。推而广之，对于任何非负整数$m$和$n$,相距$mg+nh$的任何一对元素都必有序，故$S$必然$mg+nh$有序。

有序性的保持和加强

在分别做过$g$排序和$h$排序之后，该向量必定$g+h$有序。对于$g$和$h$的任一线性组合，该向量也应$mg+nh$有序，因此反过来，逆序对之间的间距绝不可能是$g$和$h$的组合。只要$g$和$h$互素，逆序对的间距就绝不可能大于$(g-1)(h-1)$。

希尔排序过程中向量的有序性之所以会不断改善，其原因为向量中每个元素所能参与构成的逆序对持续减少。于此同时，底层所采用的插入排序算法的实际执行时间将不断减少。

若某向量S已属于$(g,h)$有序，假设$g$和$h$的数量级均处于$O(d)$数量级。以下考查对该向量做$d$排序所需的时间。

根据定义，$d$排序将$S$等间距地划分为长度各为$O(n/d)$的$d$个子向量，并分别排序，在$(g,h)$有序的向量中，逆序对的间距不超过$(g-1)(h-1)/d=O(d)$ 。

于是，再次根据插入排序的结论，插入排序可在$O(d)O(n/d)=O(n)$时间内完成每一子向量的排序，所有子向量的排序应该不超过$O(dn)$。

PS序列

$H_{PS}=H_{shell}-1={2^k-1|k \in N}={1,3,15,31,63,127,255}$

其中相邻两项的确互素，采用这一序列，希尔排序的算法可达到$O(n^{3/2})$ ，其中$n$为待排序向量的规模。

在PS序列中，设$W_t$为其中$n^{1/2}$ 最接近者，亦即是$W_t=\Theta(n^{1/2})$ 。以下将希尔排序过程中所有的迭代分为两类，分别估计其运行时间。

首先，考查在$W_t$之前执行的各步迭代。

此类迭代所对应的增量均满足$W_k>W_t$。在每一次这类迭代中，矩阵共有$W_k$列，各列包含$O(n/W_k)$个元素。因此，若采用插入排序算法，各列耗时$O((n/W_k)^2)$ ,所有列共计$O(n^2/W_k)$。于是，此类迭代各自所需的时间$O(n^2/(W_k))$构成一个以大致以2为比例的等比级数，其总和应线性正比于其中最大的一项，亦即不超过$O(2n^2/W_t)=O(n^{3/2})$。

对称地，再来考查$W_t$之后的各步迭代，

这类迭代所对应的增量均满足$W_k<W_t$ ,考虑到此前刚完成$W_{k+1}$排序和$W_{k+2}$排序，来自PS序列的$W_{k+1}$和$W_{k+2}$互素，且与$W_{k}$同处一个数量级，根据之前的结论，每一次这样的迭代至多需要$O(nW_{k})$时间。同样地，这类迭代所需的时间$O(nW_{k})$同样构成一个大致以2为比例的等比级数，其总和也应线性正比于其中最大的一项，亦即不超过$O(2nW_{t})=O(n^{3/2})$。

Pratt序列

$H_{pratt}={2^p3^q|p,q\in N}={1,2,3,4,8,9,12,36,…}$

采取pratt序列，希尔序列算法至多运行$O(nlog^2n)$时间

在$(2,3)$有序的序列中，逆序元素之间的间距不超过$(2-1)(3-1)-1=1$。

整个向量的逆序对不超过$O(n)$个，对该向量的$1$排序仅需$ O(n)$时间。

对于pratt序列，若S已是$(2h_k,3h_k)$有序，故若按照相对于$h_k$的模余值，可以划分为$h_k$个同余类；相应地，原整个向量可拆分为$h_k$个等长的子向量。其中每个元素都是$(2,3)$有序的，根据以上结论，可在线性时间内转化为$1$有序的，总体效果而言，等同于在$O(n)$时间内转化为全局的$h_k$有序。

pratt序列中大于$n$的项数至多不超过$log_2nlog_3n=o(log^2n)$。

Sedgewick序列

Pratt序列效率比较高，但因其中各项的间距太小，会导致迭代趟数过多，为此，Sedgewick提出了以下增量序列：

${1,5,19,41,109,209,505,929,2161,3905,8929,…}$

其中各项均为$94^k-92^k+1$的形式，如此改进之后，希尔排序算法在最坏情况下的复杂度为$n^{4/3}$,平均复杂度为$O(n^{7/6})$。更重要的是，在通常应用环境中，这一增量序列的综合效率最佳。

排序方法 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 $O( n^2)$ $ O(n)$ $ O(1)$ 输入敏感，稳定
插入排序 $O( n^2)$ $ O(n^2)$ $ O(1) $ 输入敏感，稳定
选择排序 $o(n^2)$ $ O(n^2) $ $ O(1) $ 输入不敏感，稳定
归并排序 $O( nlogn)$ $O( nlogn)$ $ O(1)$ 输入不敏感，稳定
快速排序 $O( n^2)$ $O (nlogn) $ $ O(1)$ 输入不敏感，不稳定
桶排序 $ O(n+M)$ $ O(n+M)$ $ O(n+M)$ 输入不敏感，稳定
基数排序 $O(t(n+M))$ $ O(t(n+M))$ $O(M)$ 输入不敏感，稳定
计数排序 $ O(n) $ $ O(M) $ $ O(M)$ 输入不敏感，稳定
锦标赛排序 $O( nlogn )$ $O( nlogn )$ $ O(n) $ 输入不敏感，稳定
就地堆排序 $O( nlogn )$ $O( nlogn )$ $ O(1)$ 输入不敏感，不稳定
shell排序 不详 不详 $ O( 1) $ 底层排序算法为输入敏感算法

以上不稳定的算法均可通过合成数的方法转换为稳定的算法，转换需要$ O(n) $时间，以上复杂度不低于$O(n)$的算法复杂度仍与之前一致。