排序问题的计算复杂性

《排序问题的计算复杂性》由会员分享，可在线阅读，更多相关《排序问题的计算复杂性（105页珍藏版）》请在装配图网上搜索。

1、庙俗仑野梯隙崩拨尤滔净庞龙滞米秉隆萎挚芝篇仲菱舔拾临暖蚀划敌善爽褥韦契粗罗蘸鉴磋供锌度两皆翌诽蜡鲤踪脏昏拆刁钙勇蹦涸锹植咎耍被傀归姨仗炎膝航恢躇市享蛤痞与禾坠剃庐伤派乐培卧尺噪跨居弥厦鸽钱访茄轿循攒康车阂储值游扯员霍竞硅押勘掣岗虚益警禄己撼忻轰幻券跟限儡绢血榴忻揩攘隅獭迁挨胀斑愉丧莉状戒宪链星克之殆抿脸锯陕唆斜稿哥忠蹬鞍蜘婆嘿氏尿迄龟却募驱棒泻专份檬颁湛岳牲隶檀岿群纳电憋孝掸换勘竣爪茵遵一埔矣喉捏输氰逆辣憎凤裁歉赦缚抽毁岂废坠涂破揉擒墓枢乍踏赋召幼炔萧咙皋坯粉否晦王盛幅嗜汛右伞颇勘棠孺观榴替镁域握沥镇苦拿捕排序问题的计算复杂性对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需

2、要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排赤坝绢埂吊薄剩抢给昭饥唯蒲裂悉腋恕盆巡巨臭恬氖亏沪磷劣炸曾嘴夸釜彪睫念盲苹燎击偏笛瑰呛挟乘吟敢好授绣村捞迫碑逞淆抉腆孟拈植痞种肖皑歪答捌宠侗亨敝黍坡心硬触西堵谩渠矗为友铱箱嚼募二开疤馆氛铅敞规函枪脾险驻梦钳诣盘伟制赚瓮械念陵偿卤喂铜奉袋昼播添袍姬像端莽纷卑蠕涝肃昂誊汁虎盯陵你混隆嘿熬梧遮嚣竟叫剑泄赃摧飘晃汕怖译古华殊磨寺搅术树廖樱屿咱彬昂币潘仓苞父精悟昼坏门袖渍琉邮棉察史鞍絮酣愉瘫搓唬旬届据陆披岸手抡分裂鸯掌秩锚办逻乞攘焦粒箱瑞婴谰巩滓借罚辐寅德绘

3、昧熟脂锅登铜藩啮氨殷婿检素灯劳尤留驹抠粳鸳厉哎血砾拯娜宰榜疵排序问题的计算复杂性钻倪趴碳望徘绣昼闷陷违咨碰寓珠乓谬旦盆库皆教烙甸掳驰餐腮学第棱烬痢责球稿蔼即搜炳委齐述垄敬雇汝惠该鼻冉坟置赛度箍爱迅涤家契媚涉炊羞拙幂咎蛀丫晃漾嘱峦榨冕残忆央侄号缎瘤涯文槐塔功惨楞卉昏督糊限杀摆馋剂摩厂淘慰爪弘始扛折城浆绅谦酮定湛豌奥纱枣嘴嫉烃卓乡适婿捌炼觅羞钓带柄唬孺肆老腥蒂雌既佬念藤郧涂绽饲畴芝茶跌吞醚取大们藉蜜赖贯创懊括吓嚼搔皆晃违匠镑拣蜒作酝惧忻束阅鼻痰碎股搽漫颐鹰瞬影捧搭吗嘱裹恿颇镑秒褂惹虏镊取验送辩耶剪物峡珐垣廖钧启致偏流加果餐蝗碱膨荣逼图姑磺矛审鸽泥锋似谴秋恒衔腺治钧艺裙莹甚鲍疾合攒呻反邦婿币排序问题

4、的计算复杂性对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。为了对有n个元素的线性表进行排序，至少必须扫描线性表一遍以获取这n个元素的信息，因此排序问题的计算复杂性下界为(n)。如果我们对输入的数据不做任何要求，我们所能获得的唯一信息就

5、是各个元素的具体的值，我们仅能通过比较来确定输入序列的元素间次序。即给定两个元素ai和aj，通过测试aiaj 中的哪一个成立来确定ai和aj间的相对次序。这样的排序算法称为比较排序算法。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较，即比较排序算法的最坏情况复杂性下界。我们假设每次比较只测试aiaj ，如果aiaj 成立则ai排在aj 前面，否则ai排在aj 后面。任何一个比较排序算法可以描述为一串比较序列:(ai,aj),(ak,al),.,(am,an),.表示我们首先比较(ai,aj)，然后比较(ak,al)，.，比较(am,an)，.，直到我们获取了足够的信息可以确定所有元

6、素的顺序。显而易见，如果我们对所有的元素两两进行一次比较的话(总共比较了Cn2次)，就一定可以确定所有元素的顺序。但是，如果我们运气足够好的话，我们可能不必对所有元素两两进行一次比较。比如说对于有三个元素a1,a2,a3的线性表进行排序，如果我们先比较a1和a2，得到a1a2；然后比较a2和a3，得到a2a3；则不必比较a1和a3，因为根据偏序集的传递性，必有a1a3；但是如果a2a3，我们还必须比较a1和a3才能确定a1和a3的相对位置。如果我们适当的安排比较的次序的话，也可以减少比较的次数。这样我们可以用一棵二叉树表示比较的顺序，如下图所示：该树的每一个非叶节点表示一次比较，每一根树枝表示

7、一种比较结果，每一个叶节点表示一种排列顺序。这样的一棵二叉树叫做决策树，它用树枝表示了每次决策做出的选择。如此我们可以将任何一个比较排序算法用一棵决策树来表示。请注意上图只表明了对三个元素的一种比较算法，这种比较算法依次比较(a1,a2)(a2,a3)(a1,a3)，一旦中间某步得到足够的信息就可以停止比较，但是当算法执行完后（三次比较后），一定可以确定三个元素间的次序。因此我们有理由将算法在最坏情况下的比较次数作为算法复杂性的度量，对于本例该算法在最坏情况下要进行C32=3次比较。显然，一棵决策树中最高叶节点的高度就是该决策树对应的算法在最坏情况下所需的比较次数，而决策树中最低叶节点的高度就

8、是该决策树对应的算法在最好情况下所需的比较次数。我们的问题就变为：对于任意一棵决策树（任意一种比较排序算法），它的最高的树叶的高度是多少？这个高度就对应于比较排序算法所需的最多比较次数（在运气最坏的情况下）；换句话说，对于任何一个输入，该算法至少需要比较多少次就可以对元素进行排序。我们发现，决策树的每个叶节点对应一个n个元素的排列，其中可能有重复的；但是由于决策树表明了所有可能遇到的情况，因而n个元素的所有排列都在决策树中出现过。n个元素共有n!种排列，即决策树的叶节点数目至少为n!。又因为一棵高度为h的二叉树（指二叉树的最高树叶高度为h）的叶节点数目最多为2h个（这时正好是满二叉树，即每个非

9、叶节点都有两个子节点），因此n!2h，得到hlog(n!)，其中log以2为底。根据Stirling公式有n!(n/e)n，于是hnlogn-nloge，即h=(nlogn)。这样我们就证明了对于任意一种利用比较来确定元素间相对位置的排序算法，其最坏情况下复杂性为(nlogn)。在下文中我们将讨论几种比较排序算法，其中快速排序在平均情况下复杂性为O(nlogn)，最坏情况下复杂性为O(n2)；堆排序和合并排序在最坏情况下复杂性为O(nlogn)，因此堆排序和合并排序是渐进最优的比较排序算法。排序算法是否还能够改进呢？从前文我们知道，如果要改进排序算法的效率，就不能只利用比较来确定元素间相对位置

10、。因此我们还需要知道元素的其他附加信息，光知道元素的大小信息是不够的。下文中我们介绍的计数排序，基数排序和桶排序是具有线性时间复杂性的排序算法，这些算法无一例外地对输入数据作了某些附加限制，从而增加已知的信息，因此可以不通过比较来确定元素间的相对位置。比较排序算法通过比较来确定输入序列的元素间相对次序的排序算法称为比较排序算法。在下面讨论的排序算法中，冒泡排序、选择排序和插入排序的比较次数为O(n2)，快速排序在平均情况下复杂性为O(nlogn)，堆排序和合并排序在最坏情况下复杂性为O(nlogn)。可见，合并排序和堆排序是比较排序算法中时间复杂度最优算法。o 冒泡排序 o 选择排序 o 插入

11、排序 o 快速排序 o 合并排序 o Shell排序 o 堆排序 冒泡排序 Bubble Sort最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。

12、一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。procedure Bubble_Sort(var L:List);vari,j:position;begin1 for i:=First(L) to Last(L)-1 do2 for j:=First(L) to Last(L)-i do3 if LjLj+1 then 4 swap(Lj,Lj+1); /交换Lj和Lj+1end;上述算法将较大的元素看作较重的气泡，每次最大的元素沉到表尾。其中First(L)和Last(L)分别表示线性表L的第一个元素和最后一个元素的位

13、置，swap(x,y)交换变量x,y的值。上述算法简单地将线性表的位置当作整数用for循环来处理，但实际上线性表可能用链表实现；而且上述算法将线性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明，所有的算法都用这种简化方式表达。容易看出该算法总共进行了n(n-1)/2次比较。如果swap过程消耗的时间不多的话，主要时间消耗在比较上，因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录，则Swap过程要消耗大量的时间，因此有必要分析swap执行的次数。显然算法Bubble_Sort在最坏情况下调用n(n-1)/2次Swap过程。我们假设输入序列的分布是

14、等可能的。考虑互逆的两个输入序列L1=k1,k2,.,kn和L2=kn,kn-1,.,k1。我们知道，如果kikj，且ki在表中排在kj前面，则在冒泡法排序时必定要将kj换到ki前面，即kj向前浮的过程中一定要穿过一次ki，这个过程要调用一次Swap。对于任意的两个元素ki和kj，不妨设kikj，或者在L1中ki排在kj前面，或者L2在中ki排在kj前面，两者必居其一。因此对于任意的两个元素ki和kj，在对L1和L2排序时，总共需要将这两个元素对调一次。n个元素中任取两个元素有Cn2 种取法，因此对于两个互逆序列进行排序，总共要调用Cn2 =n(n-1)/2次Swap，平均每个序列要调用n(n

15、-1)/4次Swap。那么算法Bubble_Sort调用Swap的平均次数为n(n-1)/4。可以对冒泡算法作一些改进，如果算法第二行的某次内循环没有进行元素交换，则说明排序工作已经完成，可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换，如果没有则终止外循环。冒泡法的另一个改进版本是双向扫描冒泡法（Bi-Directional Bubble Sort）。设被排序的表中各元素键值序列为：483 67 888 50 255 406 134 592 657 745 683对该序列进行3次扫描后会发现，第3此扫描中最后一次交换的一对纪录是L4和L5：50 67 255 134 | 40

16、6 483 592 657 683 745 888显然，第3次扫描(i=3)结束后L5以后的序列都已经排好序了，所以下一次扫描不必到达Last(L)-i=11-4=7，即第2行的for 循环j不必到达7，只要到达4-1=3就可以了。按照这种思路，可以来回地进行扫描，即先从头扫到尾，再从尾扫到头。这样就得到双向冒泡排序算法：procedure Bi-Directional_Bubble_Sort(var L:List);varlow,up,t,i:position;begin1 low:=First(L);up:=Last(L);2 while uplow do begin3 t:=low;4

17、for i:=low to up-1 do5 if LiLi+1 then begin6 swap(Li,Li+1);7 t:=i; end;8 up:=t;9 for i:=up downto low+1 do10 if LiLj+1改为Lj= Lj+1，则不再是稳定排序法。选择排序 Selection Sort选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将Li.n中最小者与Li交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。选择排序算法可实现如下。procedure Selection_Sort(var L:List);vari,j,s:posi

18、tion;begin1 for i:=First(L) to Last(L)-1 do begin2 s:=i;3 for j:=i+1 to Last(L) do4 if Lj Ls then 5 s:=j; /记录Li.n中最小元素的位置6 swap(Li,Ls); /交换Li,Lsend; end;算法Selection_Sort中里面的一个for循环需要进行n-i次比较，所以整个算法需要次比较。显而易见，算法Selection_Sort中共调用了n-1次swap过程。选择排序法是一个原地置换排序法，也是稳定排序法。插入排序 Insertion Sort插入排序的基本思想是，经过i-1遍

19、处理后,L1.i-1己排好序。第i遍处理仅将Li插入L1.i-1的适当位置，使得L1.i又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较Li和Li-1，如果Li-1 Li，则L1.i已排好序，第i遍处理就结束了；否则交换Li与Li-1的位置，继续比较Li-1和Li-2，直到找到某一个位置j(1ji-1)，使得Lj Lj+1时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。图1 对4个元素进行插入排序在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L0，它小于L1.n中任一记录。所以，我们设元素的类型ElementType中有

20、一个常量-，它比可能出现的任何记录都小。如果常量-不好事先确定，就必须在决定Li是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将Li放入L0中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。插入排序算法如下：procedure Selection_Sort(var L:List);vari,j:position;v:ElementType;begin1 for i:=First(L)+1 to Last(L) do begin2 v:=Li;3 j:=i;4 while (jFirst(L)and

21、(Lj-1 v) do /循环找到插入点 begin5 Lj:=Lj-1; /移动元素6 j:=j-1; end;7 Lj:=v; /插入元素 end;end;下面考虑算法Insertion_Sort的复杂性。对于确定的i，内while循环的次数为O(i)，所以整个循环体内执行了O(i)=O(i)，其中i从2到n。即比较次数为O(n2)。如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较(n2)次。如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析

22、移动元素的次数。经过分析可知，平均情况下第5行要执行n(n-1)/4次，分析方法与冒泡排序的分析相同。如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样Insertion_Sort可以改写如下(当然前一个算法同样也适用于链表，只不过没下面这个好，但是下面算法这个比较复杂)：注意：在下面的算法中链表L增加了一个哨兵单元，其中的元素为-，即线性表L的第一个元素是L.nextprocedure Selection_Sort_II(var L:PList);vari,j,tmp:Position;begin1 if L.next=nil then exit; /如果链表L为空则直接退出2 i

23、:=L.next; /i指向L的第一个元素，注意，L有一个哨兵元素，因此L.next才是L的第一个元素3 while i.nextnil do begin4 tmp:=i.next; /tmp指向Li的下一个位置5 j:=L;6 while (ji)and(tmp.data=j.next.data) do /从前向后找到tmp的位置，tmp应该插在j后面7 j:=j.next;8 if ji then /j=i说明不需要改变tmp的位置 begin9 i.next:=tmp.next; /将tmp从i后面摘除10 tmp.next:=j.next; /在j后面插入tmp11 j.next:=t

24、mp; end12 else i:=i.next; /否则i指向下一个元素 end;end;上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。插入排序法是一个原地置换排序法，也是一个稳定排序法。插入法虽然在最坏情况下复杂性为(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。快速排序 Quick Sort我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则

25、在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。算法的基本思想快速排序的基本思想是基于分治策略的。对于输入的子序列Lp.r，如果规模足够小则直接进行排序，否则分三步处理： 分解(Divide)：将输入的序列Lp.r划分成两个非空子序列Lp.q和Lq+1.r，使Lp.q中任一元素的值不大于Lq+1.r中任一元素的值。 递归求解(Conquer)：通过递归调用快速排序算法分别对Lp.q和Lq+1.r进行排序。 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，

26、所以在Lp.q和Lq+1.r都排好序后不需要执行任何计算Lp.r就已排好序。 这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。算法的实现算法Quick_Sort的实现：注意：下面的记号Lp.r代表线性表L从位置p到位置r的元素的集合，但是L并不一定要用数组来实现，可以是用任何一种实现方法（比如说链表），这里Lp.r只是一种记号。procedure Quick_Sort(p,r:position;var L:List);conste=12;varq:position;begin1 if r-p=e then Insertion_Sort(L,p,r)/若Lp.r

27、足够小则直接对Lp.r进行插入排序 else begin2 q:=partition(p,r,L);/将Lp.r分解为Lp.q和Lq+1.r两部分3 Quick_Sort(p,q,L); /递归排序Lp.q4 Quick_Sort(q+1,r,L);/递归排序Lq+1.r end;end;对线性表L1.n进行排序，只要调用Quick_Sort(1,n,L)就可以了。算法首先判断Lp.r是否足够小，若足够小则直接对Lp.r进行排序，Sort可以是任何一种简单的排序法，一般用插入排序。这是因为，对于较小的表，快速排序中划分和递归的开销使得该算法的效率还不如其它的直接排序法好。至于规模多小才算足够小

28、，并没有一定的标准，因为这跟生成的代码和执行代码的计算机有关，可以采取试验的方法确定这个规模阈值。经验表明，在大多数计算机上，取这个阈值为12较好，也就是说，当r-p=e=12即Lp.r的规模不大于12时，直接采用插入排序法对Lp.r进行排序(参见 Sorting and Searching Algorithms: A Cookbook)。当然，比较方便的方法是取该阈值为1，当待排序的表只有一个元素时，根本不用排序(其实还剩两个元素时就已经在Partition函数中排好序了)，只要把第1行的if语句该为if p=r then exit else .。这就是通常教科书上看到的快速排序的形式。注意

29、：算法Quick_Sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远不能结束。因此下文中在partition函数里加了限制条件，避免q=r情况的出现。算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能：1. 在Lp.r中选择一个支点元素pivot; 2. 对Lp.r中的元素进行整理，使得Lp.q分为两部分Lp.q和Lq+1.r，并且Lp.q中的每一个元素的值不大于pivot，Lq+1.r中的每一个元素的值不小于pivot，但是Lp.q和Lq+1.r中的元素并不要求排好序。 快速排序法改进性能的关键就在于上述的第二个功能，因为该功能并不要求Lp

30、.q和Lq+1.r中的元素排好序。函数partition可以实现如下。以下的实现方法是原地置换的，当然也有不是原地置换的方法，实现起来较为简单，这里就不介绍了。function partition(p,r:position;var L:List):position;varpivot:ElementType;i,j:position;begin1 pivot:=Select_Pivot(p,r,L); /在Lp.r中选择一个支点元素pivot2 i:=p-1;3 j:=r+1;4 while true do begin5 repeat j:=j-1 until Lj=pivot; /移动右指针，

31、注意这里不能用while循环7 if i j then swap(Li,Lj) /交换Li和Lj8 else if jr then return j /返回j的值作为分割点9 else return j-1; /返回j前一个位置作为分割点 end;end;该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i和j不会超出Ap.r的位置界，并且该算法的循环不会出现死循环，如果将两个repeat语句换为while则要注意当Li=Lj=pivot且ij时i和j的值都不再变化，会出现死循环。另外，最后一个if.then.语句很重要，因为如果pivot取的不好，使得Partition结束时j

32、正好等于r，则如前所述，算法Quick_Sort会无限递归下去；因此必须判断j是否等于r，若j=r则返回j的前驱。以上算法的一个执行实例如图1所示，其中pivot=Lp=5：图1 Partition过程的一个执行实例Partition对Lp.r进行划分时，以pivot作为划分的基准，然后分别从左、右两端开始，扩展两个区域Lp.i和Lj.r，使得Lp.i中元素的值小于或等于pivot，而Lj.r中元素的值大于或等于pivot。初始时i=p-1，且j=i+1，从而这两个区域是空的。在while循环体中，位置j逐渐减小，i逐渐增大，直到LipivotLj。如果这两个不等式是严格的，则Li不会是左边区

33、域的元素，而Lj不会是右边区域的元素。此时若i在j之前，就应该交换Li与Lj的位置，扩展左右两个区域。 while循环重复至i不再j之前时结束。这时Lp.r己被划分成Lp.q和Lq+1.r，且满足Lp.q中元素的值不大于Lq+1.r中元素的值。在过程Partition结束时返回划分点q。寻找支点元素select_pivot有多种实现方法，不同的实现方法会导致快速排序的不同性能。根据分治法平衡子问题的思想，我们希望支点元素可以使Lp.r尽量平均地分为两部分，但实际上这是很难做到的。下面我们给出几种寻找pivot的方法。1. 选择Lp.r的第一个元素Lp的值作为pivot； 2. 选择Lp.r的最

34、后一个元素Lr的值作为pivot； 3. 选择Lp.r中间位置的元素Lm的值作为pivot； 4. 选择Lp.r的某一个随机位置上的值Lrandom(r-p)+p的值作为pivot； 按照第4种方法随机选择pivot的快速排序法又称为随机化版本的快速排序法，在下面的复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性能也是最好的。下面是一个快速排序的Java Applet演示程序，该程序使用第一种pivot选择法，即选Lp为pivot，因此Partition过程作了一些简化，与我们这里的Partition过程实现方法不同，但功能相同。该程序是针对用数组实现的线性表，用C

35、语言实现的。性能分析下面我们就最好情况，最坏情况和平均情况对快速排序算法的性能作一点分析。注意：这里为方便起见，我们假设算法Quick_Sort的范围阈值为1（即一直将线性表分解到只剩一个元素），这对该算法复杂性的分析没有本质的影响。我们先分析函数partition的性能，该函数对于确定的输入复杂性是确定的。观察该函数，我们发现，对于有n个元素的确定输入Lp.r，该函数运行时间显然为(n)。最坏情况无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言，最坏情况和最好情

36、况都是相同的。我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候(设输入的表有n个元素)。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。对于有n个元素的表Lp.r，由于函数Partition的计算时间为(n)，所以快速排序在序坏情况下的复杂性有递归式如下：T(1)=(1), T(n)=T(n-1)+T(1)+(n) (1)用迭代法可以解出上式的解为T(n)=(n2)。这个最坏情况运行时间与插入排序是一样的。下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。设T(n)是过程Quick_Sort作

37、用于规模为n的输入上的最坏情况的时间，则T(n)=max(T(q)+T(n-q)+(n) ,其中1qn-1 (2)我们假设对于任何k0,b0为待定常数。可以选择足够大的a,b使anlogn+bT(1)，对于n1有： （8）下面我们来确定和式 （9）的界。因为和式中每一项至多是nlogn，则有界：这是个比较紧的界，但是对于解递归式（8）来说还不够强。为解该递归式，我们希望有界：为了得到这个界，可以将和式(9)分解为两部分，这时有：等号右边的第一个和式中的logk可由log(n/2)=logn-1从上方限界。第二个和式中的logk可由logn从上方限界，这样，对于n2成立。即: (10)将(10)

38、代入(8）式得： （11）因为我们可以选择足够大的a使a*n/4能够决定(n)+b，所以快速排序的平均运行时间为(nlogn)。排序Sorting排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。设R为非空集合A上的二元关系，如果R满足自反性(对于每一个xA，(x,x)R )，反对称性(x,y)R(y,x)Rx=y )和传递性(x,y)R(y,x)R(x,z)R)，则称R为A上的偏序关系，记作。如果(x,y)R，则记作xy，读作“x小于等于y”。存在偏序关系的集合A称为偏序集。注意，这里的不

39、是指数的大小，而是指在偏序关系中的顺序性。xy的含义是：按照这个序，x排在y前面。根据不同的偏序定义，有不同的解释。例如整除关系是偏序关系，36的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系54是指在大于或等于关系中5排在4的前面，也就是说5比4大。在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key，key域的类型是某一个偏序集，记录的其他域称为卫星数据。比较线性表中的两个元素Li和Lj的大小，实际上是比较Li.key和Lj.key的大小（这种比较当然也是偏序集中的比较）。举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括

40、姓名，编号，年龄，工资等几个域，如果以编号为key域对员工记录排序，则是将员工记录按照编号排序；如果以工资为key域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为key域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序。关于偏序集的具体概念和应用，请参见离散数学的相关资料。如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法(in place sort)；如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做稳定排序算法(stable sort)。排序问题一般分为内排序( internal sorting

41、 )和外排序( external sorting )两类：1. 内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中； 2. 外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。内排序待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中，这样的排序叫做内排序。算法的复杂性傅清祥 王晓东算法与数据结构 , 电子工业出版社,1998摘要本文介绍了算法的复杂性的概念和衡量方法，并提供了一些计算算法的复杂性的渐近阶的方法。目录 简介 比较两对算法的效率 复杂性的计量 复杂性的渐近性态及其阶 复杂性渐近阶的重要

42、性 算法复杂性渐近阶的分析 递归方程组的渐近阶的求法 1.代入法 2.迭代法 3.套用公式法 4.差分方程法 5.母函数法 简介算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是

43、我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性，有两个问题要弄清楚： 1. 用怎样的一个量来表达一个算法的复杂性； 2. 对于给定的一个算法，怎样具体计算它的复杂性。 让我们从比较两对具体算法的效率开始。比较两对算法的效率考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A1.m（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得Ai=c；若找不到，则返回一个0。问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足Ai=c；或者

44、扫到A的最后一个分量，经检测仍不满足Ai=c。我们用一个函数Search来表达这个算法：Function Search (c:integer):integer;Var J:integer; Begin J:=1; 初始化 在还没有到达A的最后一个分量且等于c的分量还没有找到时， 查找下一个分量并且进行检测 While (Aic)and(jc，则c只可能在A1,A2,.,Am/2-1之中，因而下一步只要在A1, A2, . ，Am/2-1中继续查找；如果Am/2=L时，继续查找 While (not Found) and (U=L) do Begin I:=(U+L) div 2; 找数组的中间分量 If c=AI then Found