大话排序

伟大的计算机科学家D.E.Knuth曾指出,四分之一以上的CPU时间都用于执行同一类型的计算:按照某种约定的次序,将给定的一组元素顺序排列,比如将n个整数按通常的大小次序排成一个非降序列。这类操作统称排序(sorting)。

在进行排序的相关讨论之前,首先我们应该知道一些术语,如下:

给定有待排序的n个项目:R1,R2,…,Rn,我们称这些项目为记录,并称n个记录的整个集合为一个文件。每个记录Rj有一个键码Kj,它支配着排序的过程。在一个记录中,除这个键码外,还可能有其他的信息;这些额外信息,除非必须作为记录的一部分来一起处理,否则对于排序过程没有影响。在键码上确定一个次序关系“<”,使得对于任意三个键码值a,b,c,下列条件成立:

  1. a<b,a=b,b<a,三个可能性中恰有一个可能性成立(这是三分律)。
  2. 如果a<b,而且b<c,则a<c(这是熟知的传递律)。

性质1和2表征了线性次序的数学概念,也称作全序。排序的目标,是确定下标为[1,2,…,n]的一个排列p(1)p(2)…p(n),它以非递降的次序来放置所有的键码:Kp(1)≤Kp(2)≤…≤Kp(n)。如果我们提出进一步的要求,即具有相同键码的记录保留它们原来的相对次序,则称这个排序是稳定的。换句话说,稳定排序有下列附加的性质,即p(i)<p(j),每当Kp(i)=Kp(j)且i<j时。

排序一般可分为内部排序外部排序。在内部排序中,记录被整个地保留在计算机的高速随机存取存储器中;当记录比内存一次所能容纳的还多时,则使用外部排序。内部排序在构造和存取数据方面具有更多的灵活性,而外部排序则告诉我们如何应对更为严格的存取约束。

排序大致分为这几种

冒泡排序

我们考察一个普遍的问题:给定n个整数,将它们按(非降)序排列。通过观察可以得出:有序(无序)序列中,任意(总有)一对相邻元素顺序(逆序)。因此我们可以采用扫描交换的策略进行排序,即:依次比较每一对相邻元素;如有必要,交换之。若整趟扫描都没有进行交换,则排序完成;否则,再做一趟扫描交换。基于这样的思路,我们有下面的冒泡排序算法:

接下来我们对此进行性能分析:

在最坏情况下,即输入数据反序排列时,此算法共需要进行n-1趟扫描交换,每趟的效果,都等同于当前有效区间循环左移一位;在第k趟中(0<k<n),需做n-k次比较和3*(n-k)次移动。

累计:#KMP = (n-1) + (n-2) + … + 1 = n(n-1)/2

#MOV = 3 * n(n-1)/2

T(n) = 4 * n(n-1)/2 = O(n2)

在最好情况下,即所有输入元素已经完全(或接近)有序时,外循环仅1次,做n-1次比较和0次元素交换。

累计:T(n) = n-1 = Ω(n)

归并排序

在归并排序中,我们采用一种分而治之的策略,即先把序列一分为二(此操作时间复杂度为O(1)),再将子序列递归排序(此操作时间复杂度为2*T(n/2)),最后合并有序子序列(此操作时间复杂度为O(n))。若真能如此,则整体的运行成本应该是O(nlogn)。相应的算法如下:

显然此归并排序算法的关键在于merge()函数,即二路归并(2-way merge)程序,所谓二路归并,即将两个有序序列,合并为一个有序序列:S[lo, hi) = S[lo, mi) + S[mi, hi)。下面给出merge()函数的具体定义:

接下来我们考察此函数的复杂度:

显然,算法的运行时间主要消耗于for循环,共有两个控制变量,初始时j = 0, k = 0,最终j = lb, k = lc,亦即j+k = lb+lc = hi-lo = n。观察发现,每经过一次迭代,j和k中至少有一个会加一(j+k也必至少加一),故知,merge()总体迭代不过O(n)次,累计只需线性时间!这一结论与排序算法的Ω(nlogn)下界并不矛盾——毕竟这里的B和C均已各自有序。另外值得注意的是,待归并子序列不必等长,亦即,允许lb ≠ lc,mi ≠ (lo + hi)/2。

至此,我们对归并排序做一个综合评价:

优点:

  • 实现最坏情况下最优O(nlogn)性能的第一个排序算法
  • 不需随机读写,完全顺序访问——尤其适用于列表之类的序列,磁带之类的设备
  • 只要实现恰当,可保证稳定——出现雷同元素时,左侧子向量优先
  • 可扩展性极佳,十分适宜于外部排序——海量网页搜索结果的归并
  • 易于并行化

缺点:

  • 非就地,需要对等规模的辅助空间——可否更加节省?
  • 即便输入完全(或接近)有序,仍需Θ(nlogn)时间——改进…

堆排序

堆是一个序列{k1, k2, …, kn},它满足下面的条件:

ki≤k2i并且ki≤k2i+1,当i=1,2,…,n/2,并且2i+1≤n

采用顺序方式存储这个序列,就可以将这个序列的每一个元素ki看成是一棵有n个结点的完全二叉树的第i个结点,其中ki是该二叉树的根节点。把堆对应的一维数组(即该序列的顺序存储结构)看作一棵完全二叉树的顺序存储,那么堆的特征可解释为,完全二叉树中任意分支结点的值都小于或等于它的左、右儿子结点的值。堆的元素序列中的第一个元素k1,即对应的完全二叉树根节点的值是所有元素中值最小的。堆排序方法就是利用这一点来选择最小元素。

我们考察Floyd建堆算法的效率,首先每个内部节点所需的调整时间,正比于其高度而非深度,不失一般性,考察满树:n = 2d+1 – 1

S(n) = 所有节点的高度总和

=∑i=0..d((d-i) * 2i)

=d * ∑i=0..d2i – T(n)

=d * (2d+1-1) – [(d-1) * 2d+1 + 2]

=2d+1 – (d+2)

=n – log2(n+1)

=O(n)

接下来我们考察此算法的复杂度:

初始化:heapify(),O(n),建堆

迭代:delMax(),O(logn),取出堆顶并调整复原

O(n) + n * O(logn) = O(nlogn)

至此,我们对堆排序做一个总体的评价,首先它易于理解,便于实现,其次它快速高效(尤其适用于大规模数据),另外它可就地运转,最后它不需全排序即可找出前k个词条。但是它是不稳定的。

快速排序

在快速排序中,我们也采用分而治之的策略,然而这种分而治之又和归并排序的有些许不同,它是将序列分为两个子序列:S = SL+SR(此操作时间复杂度为O(n)),两个子序列分别规模缩小:max{|SL|,|SR|} < n,又彼此独立:max(SL)≤max(SR)。在子序列分别递归的排序之后,原序列自然有序:sorted(S)=sorted(SL)+sorted(SR)。最终我们可以到达平凡解,即只剩单个元素时,本身就是解。由以上分析,我们可以看出,mergesort的计算量和难点在于,而quicksort在于。要实现上述的划分,我们可以在序列中找到一个轴点(pivot),即它的左(右)侧的元素,均不比它更大(小)。这样,以轴点为界,原序列的划分自然实现:[lo, hi) = [lo, mi) + [mi] + (mi, hi]。至此,我们可以给出下面的基本算法:

由这个基本算法,我们可知,快速排序的核心在于partition()函数,即构造轴点。关于轴点,我们有一个坏消息,即在原始序列中,轴点未必存在,例如,在乱排序列(darangement)(可以通过对一个有序序列进行循环移位得到)中轴点并不存在。但又有一个必要条件,即轴点必定已然就位,尽管反之不然。特别地,在有序序列中,所有元素皆为轴点,反之亦然。从这个角度看,快速排序就是将所有元素逐个转换为轴点的过程。至此,我们得到了一个好消息,即通过适当交换,可使任一元素转换为轴点。在构造轴点的过程中,我们可以任取一候选者(如[0]),需要用到2个指针,以此将原始序列分成3个子序列,即前缀L:≤候选者,初始为空;后缀G:≥候选者,初始为空;中段U:?待确定者,初始为全集。具体的实施过程是:交替地内向移动lo和hi,逐个检查当前元素,若更小(大),则转移归入L(G),当lo=hi时,只需将候选者嵌入于L、G之间,它即是轴点!整个过程中,各元素最多移动一次(候选者两次)——累计O(n)时间、O(1)辅助空间。不难验证,算法的不变性:L≤pivot≤G;U=[lo, hi]中,[lo]和[hi]交替空闲。具体算法如下:

接下来我们对此进行分析:

首先它是不稳定的,即lo(hi)的移动方向相反,左(右)侧的大(小)重复元素可能前(后)颠倒。其次,它只需O(1)的附加空间,在最坏情况下需要Ω(n)空间,实际上依据Sedgewick的方法可控制在O(logn)。在时间性能方面,最好情况下,每次划分都(接近)平均,轴点总是(接近)中央,此时T(n) = 2 * T((n-1)/2) + O(n) = O(nlogn),到达下界。最坏情况下,每次划分都极不均衡,比如,轴点总是最小(大)元素,此时T(n) = T(n-1) + T(0) + O(n) = O(n2),与冒泡排序相当。即便采用随机选取、(Unix)三者取中之类的策略,也只能降低最坏情况的概率,而无法杜绝。我们需要更加具体的考察其平均性能,然而幸运的是,快速排序的平均性能的确为O(nlogn)。以均匀独立分布为例:

T(n) = (n+1) + (1/n) * ∑n-1k=0[T(k) + T(n-k-1)]

= (n+1) + (2/n) * ∑n-1k=0T(k)  //乘以n…

n * T(n) = n * (n+1) + 2 * ∑n-1k=0T(k)  //下推至n-1…

(n-1) * T(n-1) = (n-1) * n + 2 * ∑n-2k=0T(k)  //相减…

n * T(n) – (n-1) * T(n-1) = 2 * n + 2 * T(n-1)  //整理…

n * T(n) – (n+1) * T(n-1) = 2 * n  //除以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

=(2 * ln2) * logn = 1.39 * logn

希尔排序

希尔排序是将整个序列视作一个矩阵,逐列各自排序,如果矩阵当前宽度为w,那么我们就将所有这w列各自的排序总称为w-sorting。每一次希尔排序的过程都是由若干个宽度不同的w-sorting组成的。当w=1时,我们又称之为1-sorting。如果矩阵的每一列都已经过排序,我们就称之为w-ordered。实际上,希尔排序的过程正是由粗到细:重排矩阵,使其更窄,再次逐列排序w-ordered;逐步求精:如此往复,直至矩阵变成一列1-sorting的过程。另外,由各矩阵宽度构成的逆序列称之为步长序列(step sequence),如h={w1=1, w2, w3, …, wk, …},我们注意到,在算法的执行过程中,我们所采用的矩阵宽度会逐步的递减,所以希尔排序算法也称作为递减增量(diminishing increment)法。它的正确性似乎是不言而喻的,因为最后一次迭代,等同于全排序。实际上,要实现矩阵重排,借助一维向量足矣,在每步迭代中,若当前的矩阵宽度为w,则B[i][j] = A[iw+j]或A[k] = B[k/w][k%w]。另外,各序列内部的排序必须采用输入敏感的算法,以保证有序性可持续改善,且总体成本足够低廉,比如,insertionsort,其实际运行时间,更多地取决于输入序列所含逆序对的总数。shellsort的总体效率取决于具体使用何种步长序列h。

我们要考察的第一个步长序列,就是由shell本人所提出的,我们也称之为希尔序列(shell’s sequence)。它是这样的:hshell={1,2,4,8,…,2k,…},采用hshell,在最坏情况下需要运行Ω(n2)时间。我们可以考察由子序列A=unsort[0,2N-1]和B=unsort[2N-1,2N]交错而成的序列:

11  14  10  15  9  8  13  12

4   3   0   1  6  7   2   5

在2-sorting刚结束时,A和B必然各自有序:

8   9  10  11  12  13  14  15

0   1   2   3   4   5  6   7

然而,其中的逆序对仍然很多,1-sorting仍需1+2+…+2N-1=Ω(n2)时间,根源就在于,hshell中各项并不互素,甚至相邻项也非互素。

对于任何一对互素的g和h,我们将不能由它们线性组合生成的数汇成一个集合并记做N(g, h),并将集合中的最大值记做x(g, h)。根据数论中的结论,x(g, h) = (g-1)*(h-1) – 1 = gh – g – h。

在某个序列中,如果任何一对距离为h的元素都保持前小后大的次序,我们就称它为h-ordered。也就是以h为间隔是有序的。当然作为其中的一个特例,在任何一个1-ordered序列中,根据定义任何一对相邻的元素彼此之间都是顺序的。任何1-ordered的序列也必然是全局有序的。任何一个序列在做过h-sorting之后,必然是h-ordered的。在希尔排序中,每向前迭代一步,对应的矩阵宽度都会相应的减少。比如,从前一轮的g减少为后一轮的h,在经过前一轮的逐列排序之后,整个序列应该是g-ordered,而在后一轮的逐列排序之后,这个序列也自然的应该是h-ordered,那么在整个序列达到以h为间隔有序的同时,此前以g为间隔的有序性是否能够依然得以延续呢?Knuth指出任何一个原先已是g-ordered的序列,在此后经过h-sorting之后,依然保持是g-ordered。也就是说相对于任何一个固定间隔而言的有序性,在希尔排序的过程中,将会不断的保持并且持续的积累下来。如果待排序序列既是g-ordered,同时也是h-ordered,这样的序列也称作是(g, h)-ordered。实际上,这样的序列也必然是(g+h)-ordered和(mg+nh)-ordered(m,n∈N)。因此,凡是间距可以表示为线性组合的任何一对元素必然是顺序的。如果g和h是互素的,而且整个序列已经是同时关于g和h有序的,那么相对于序列中秩为i的元素,可能逆序的元素无非就是不能由g和h线性组合生成的那个最大的整数,即(g-1)*(h-1),而随着希尔排序的不断迭代,g和h都会不断的减小,这就表示逆序对的总数会不断持续的减少。这就是为什么在希尔排序的底层更加倾向于使用插入排序算法的原因,因为插入排序具有输入敏感性,它的实际运行时间将线性正比于序列中所含逆序对的总数。



发表评论

电子邮件地址不会被公开。 必填项已用*标注