DSA-6：排序算法之向量实现

之前的文章已经说过，有序性在很多场合都可以极大地提高计算的效率。想要向量有序，必须借助排序算法。本文就将从向量这一数据结构切入，介绍一下排序算法。

排序与下界

排序算法

排序算法的种类繁多，根据其处理数据的规模和存储的特点不同，可以分为内部排序算法和外部排序算法。内部排序算法处理的数据规模相对不大，内存足以容纳；外部排序算法处理的数据规模很大，必须借助外部甚至分布式存储器，在排序计算的过程中，内存只能容纳一小部分数据。

根据排序算法输入形式的不同，排序算法又可以分为离线算法和在线算法。离线算法将待排序的数据以批处理的形式整体给出；在线算法中待排序的数据需要实时生成，算法启动后数据陆续到达。

此外还可以根据依赖的体系结构不同，将排序算法分为串行和并行两类；还可以根据排序算法是否采用随机策略，将其分为确定式和随机式。

在这一系列的文章中，主要讨论确定式串行离线的内部排序算法。

下界

对于任意特定的应用问题，随着算法的改进，其效率的提高必定有一极限，因为不可能不劳而获。这一极限必然存在，其具体数值取决于应用问题本身以及其所采用的计算模型。

一般的，任一问题在最坏情况下的最低计算成本，即为该问题的复杂度下界。一旦某一算法的性能达到这一下界，就意味着它已经式最坏情况下最优的算法了。

注意，不要将问题的复杂度下界与算法的最优复杂度混淆。复杂度下界是针对特定问题而言的，处理这个问题的算法可以有很多，但是一定有一个简单到不能再简单的算法。算法的复杂度是针对特定的算法，在不同输入下，算法处理这些输入所需要的时间或者空间。

对于排序算法，可以用比较树来辅助我们确定它的复杂度下界。

比较树有点像一棵二叉树，它具有如下的性质：

• 每一内部节点各对应于一次比对操作
• 内部节点的左、右分之，分别对应于在两种比对结果下的执行方向
• 叶节点（或根节点到叶节点的路径）对应于算法某次执行的完整过程及输出
• 反过来，算法每一次运行的过程都对应于从根到某一叶节点的路径

将比较树推广到其他类型的算法上，只要其中的分支都完全取决于不同变量或常量的比对或比较结果，则该算法的所有可能执行过程都可以表示和概括为一棵比较树。反之，凡是可以如此描述的算法，都称作基于比较式的算法，简称CBA算法。

使用比较树估计下界

考察任一CBA式算法，设$CT(A)$为与之对应的一棵比较树。由此，算法A在最坏的情况下的运行时间，将取决于比较树中所有的叶节点的最大深度（称作该树的高度，记为$h(CT(A))$）。因此就渐进的意义来说，算法A的时间复杂度不低于$\Omega(h(CT(A)))$。由于算法A处理该问题的时间复杂度是确定的，那么对于其他问题，该算法处理那些问题的时间复杂度也在$\Omega(h(CT(A)))$附近。因此，这里使用了大$\Omega$记号。

任一CBA式算法都对应于某棵比较树，该问题的复杂度下界就应等于这些比较树的最小高度，而这可以通过考察树中所含的叶节点数目确定。具体的，在一棵高度为$h$的二叉树中，叶姐带你的数目不可能多于$2^h$。因此反过来，如果某一问题的输出结果不少于$N$种，则比较树中叶节点也不可能少于$N$个，树高不可能低于$\log_2N$。

考虑CBA式排序算法，就$n$个元素的排序算法而言，可能的输出共有$N = n!$种。此时，待排序的元素之间不仅可以判等还可以比较大小，因此此时的比较树应为三叉树，也即每个非叶节点都有三个分支。仿照上面的思路，任一CBA式排序算法所对应的比较树高度应为：$h\ge \lceil\log_3(n!)\rceil = \lceil\log_3e\cdot\ln(n!)=\Omega(n\log n)$。

可见，最坏情况下CBA式排序算法至少需要$\Omega(n\log n)$的时间，其中$n$为待排序元素数目。

排序算法的稳定性

在将无序向量A转换为有序向量S之后，设A[i]对应于S[ki]。若对于A中每一对重复元素A[i] = A[j]，相应的有S[ki] = S[kj]，都有i小于j当且仅当ki小于kj，那么称该排序算法是稳定算法。简而言之，稳定算法的特点是，重复元素之间的相对次序在排序前后保持一致，反之则称为不稳定算法。

在之前的文章中我们介绍过起泡排序，该算法中重复元素不会进行交换。因此，气泡排序属于稳定算法。

稳定的排序算法可以用来实现同时对多个关键码按照字典顺序的排序。

归并排序

归并排序是第一个可以在最坏情况下依然保持$\mathcal O (n\log n)$运行时间的确定性排序算法。

二路归并

归并排序可以理解为通过反复调用所谓二路归并算法实现的。所谓二路归并，指的是将两个有序序列合并称为一个有序序列。这里的有序序列既可以是向量，也可以是列表。在这里我们只考虑向量的情况。

二路归并属于迭代式算法。每步迭代中，只需要比较两个待归并有序向量的首元素，将小者取出并追加到输出向量的末尾，该元素在原向量中的后继则成为新的首元素。如此往复，直到某一向量为空。最后，将另一非空的有序输入向量整体接至输出向量的末尾。下图给出了有序向量的二路归并实例。

由此可知，二路归并算法在任何时刻都只需要载入两个向量的首元素，故除了归并输出的向量外，仅需要常数规模的辅助空间。另外该算法始终严格地按照顺序处理输入和输出向量，故特别适用于使用磁带机等顺序存储器的场合。

归并排序的实现

下面给出了归并排序算法的实现代码。

template <typename T> //向量归并排序
void Vector<T>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
   if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
   Rank mi = ( lo + hi ) / 2; //以中点为界
   mergeSort ( lo, mi ); mergeSort ( mi, hi ); //分别排序
   merge ( lo, mi, hi ); //归并
}

归并排序算法属于典型的采用了分治策略的算法。上面的代码以递归的方式实现了归并排序。

该算法将向量均匀地分为两个子向量，将这两个子向量递归地转换为有序向量后，再进行二路归并，即可将整个向量转化为有序向量。这里的递归终止条件是当前向量长度$\rm{n = hi - lo =1}$：只有一个元素的向量天然就是有序的，因此可以将这一分支作为递归基。注意，二路归并是归并排序算法的一部分，受到归并算法的调用。

下图给出了归并排序算法的一个完整实例。由图可以清晰地看出，含8个元素的向量在递归过程中不断被均分，直到到达只有一个元素的向量的递归基。然后各子向量开始层层返回，每返回一次就进行一次二路归并。最后递归返回结束，得到整体有序的向量。

二路归并的实现

下面给出了二路归并算法的代码。

template <typename T> //有序向量（区间）的归并
void Vector<T>::merge ( Rank lo, Rank mi, Rank hi ) { //[lo, mi)和[mi, hi)各自有序，lo < mi < hi
   Rank i = 0; T* A = _elem + lo; //合并后的有序向量A[0, hi - lo) = _elem[lo, hi)，就地
   Rank j = 0, lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) <-- _elem[lo, mi)
   for ( Rank i = 0; i < lb; i++ ) B[i] = A[i]; //复制自A的前缀
   Rank k = 0, lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi)，就地
   while ( ( j < lb ) && ( k < lc ) ) //反复地比较B、C的首元素
      A[i++] = ( B[j] <= C[k] ) ? B[j++] : C[k++]; //将更小者归入A中
   while ( j < lb ) //若C先耗尽，则
      A[i++] = B[j++]; //将B残余的后缀归入A中
   delete [] B; //释放临时空间
}

第7行代码中，循环在前向量B首元素的下标j和后向量C首元素的下标k都不越界时，持续向前进行，反复比较B和C的首元素。在第9行代码中，如果C的首元素下标先越界，那么就将B的残余后缀归入A中。如果是B的首元素下标先越界，那么理论上就要将C的残余后缀归入A中。但是这里C本身就在A中，因此不需要额外的移动操作了。

复杂度分析

归并排序算法的时间成本主要取决于二路归并算法。

二路归并算法merge()的时间成本取决于其中循环迭代的总次数，其迭代的次数永远不会超过输入向量的长度，也即$\mathcal O (\rm{hi - mi}) = \mathcal O (n)$。另外，无论子向量的内部元素组成及其相对大小如何，只有前后两个输入向量都归入输出向量后，迭代才能终止。因此该算法在最好的情况下仍然需要$\Omega (n)$时间。综上，二路归并算法需要的时间为$\Theta (n)$。即使两个子向量在物理上并非前后衔接，且长度相差悬殊，二路归并算法依然可行并且只需要线性时间。

前面说过，对某个特定的排序问题，无论使用何种CBA排序算法，它的复杂度下界都是$\Omega(n\log n)$，这并不与二路归并算法的时间复杂度为$\Omega (n)$矛盾。因为二路归并算法的输入并不是完全随机的无序向量，实际上它的输入已经具有相当的有序性。

基于以上分析，可以得到归并排序算法的时间复杂度。

将归并算法处理长度为$n$的向量所需要的时间记为$T(n)$。归并算法需要递归地对长度各为$n/2$的两个子向量做归并排序，然后再花费$\mathcal O (n)$时间做一次二路归并。由此可以得到：$T(n) = 2T(n/2) + \mathcal O (n)$。特别的，在递归基处有$T(1) = \mathcal O (1)$。由以上递推公式可以得到$T(n) = \mathcal O (n\log n)$。由于二路归并算法的效率稳定在$\Theta (n)$，因此更准确地讲，归并排序算法的时间复杂度应为$\Theta (n\log n)$。

归并排序算法的复杂度也可通过下面的方式分析出来。归并排序算法讲向量层层均分为子向量后，形成了一个像二叉树一样的结构。由于这个类二叉树状的结构中每层里的每个递归实例中的二路归并算法只需要线性时间，因此一层中所有递归实例消耗时间之和也是线性的$\Theta (n)$。又由于这个类二叉树状的结构一共有$\Theta \log_2n$层，因此整个归并排序算法总计需要$\Theta (n\log n)$时间。