chapter2-Sorting算法和算法的分析技术课件

chapter2Sorting算法和算法的分析技术6、露凝无游氛，天高风景澈。7、翩翩新来燕，双双入我庐，先巢故尚在，相将还旧居。8、吁嗟身后名，于我若浮烟。9、陶渊明（约365年—427年），字元亮，（又一说名潜，字渊明）号五柳先生，私谥“靖节”，东晋末期南朝宋初期诗人、文学家、辞赋家、散文家。汉族，东晋浔阳柴桑人（今江西九江）。曾做过几年小官，后辞官回家，从此隐居，田园生活是陶渊明诗的主要题材，相关作品有《饮酒》、《归园田居》、《桃花源记》、《五柳先生传》、《归去来兮辞》等。10、倚南窗以寄傲，审容膝之易安。chapter2Sorting算法和算法的分析技术chapter2Sorting算法和算法的分析技术6、露凝无游氛，天高风景澈。7、翩翩新来燕，双双入我庐，先巢故尚在，相将还旧居。8、吁嗟身后名，于我若浮烟。9、陶渊明（约365年—427年），字元亮，（又一说名潜，字渊明）号五柳先生，私谥“靖节”，东晋末期南朝宋初期诗人、文学家、辞赋家、散文家。汉族，东晋浔阳柴桑人（今江西九江）。曾做过几年小官，后辞官回家，从此隐居，田园生活是陶渊明诗的主要题材，相关作品有《饮酒》、《归园田居》、《桃花源记》、《五柳先生传》、《归去来兮辞》等。10、倚南窗以寄傲，审容膝之易安。计算机算法

——设计与分析导论南开大学 计算机科学与技术系刘璟2Chapter2. Sorting算法与算法的分析技术2.1排序(Sorting)问题2.2O(n2)阶的排序算法2.3基于相邻元比较的排序算法和希尔(Shell)排序2.4O(nlogn)阶的排序算法2.5 比较排序算法的时间复杂度下界2.6 排序算法的有关研究3计算机算法

——设计与分析导论南开大学 计算机科学与技术系刘璟2Chapter2. Sorting算法与算法的分析技术2.1排序(Sorting)问题

2.2O(n2)阶的排序算法

2.3基于相邻元比较的排序算法和希尔(Shell)排序2.4O(nlogn)阶的排序算法

2.5 比较排序算法的时间复杂度下界

2.6 排序算法的有关研究

32.1排序（Sorting）问题

有关排序的几个基本概念：1.全序集：数据集合D称为关于关系“<”的全序集，如果满足1°a<b，a=b，b<a三者必居其一；2°a<b，b<c，则a<c。全体整数集、实数集、字符串集等都是全序集。2.排序（Sorting）问题：已知：n项记录R1，R2，…，Rn，其一个域称为关键字（Key），关键字值K1，K2，…，Kn属于一全序集。要求：重排n项记录为Rπ(1)，Rπ(2)，…，Rπ(n)，其中π：π(1)，π(2)，…，π(n)，为1,…,n的一个排列，使对应的关键字满足：Kπ(1)≤Kπ(2)≤…≤Kπ(n)。43.稳定（Stable）排序算法：如果排序问题满足：若Rπ(i)=Rπ(j)

且i<j则π(i)<π(j)，则称其为稳定排序算法。稳定排序保证序列中关键字相同的记录在排序过程中不会交换次序。4.内部（Internal）排序算法：数据在高速随机存储设备上（内存）进行排序操作，这时数据间的比较和移动指令的代价一般是相同的。5.外部（External）排序算法：数据主要驻留在外部的低速存储设备（硬盘、磁带）上，数据在内存与硬盘（磁带）之间的传送、移动的代价明显高于数据比较操作，因此，外部排序算法的设计不同于内部排序。56.原址排序算法：在排序过程中除了全部输入数据所占用的空间之外，只需有限的额外空间。如果额外空间的大小与记录数n无关，则称为原址排序。7.基于关键字比较的排序算法：这类排序算法中仅对关键字进行比较和移动操作，因此关键字的比较和移动是算法的基本操作。62.2O(n2)阶的排序算法

2.2.1选择排序（SelectionSorting）

1.选择排序的思想：把待排序的L[1..n]视为两个部分：L[1..i-1]为已排序部分，L[i..n]为未排序部分。排序步骤为：

1°i=1；2°选择：在L[i..n]中求最小元L[k]，i≤k≤n；3°交换L[i]与L[k]，i++，if（i<n）goto2°；4°停止。2.算法的描述：输入：L[1..n]存放待排序元素，n(≥0)为元素个数。输出：L[1..n]按关键字递增顺序排列。算法2.1选择排序算法SelectSort73.算法的分析：

关键字的比较发生在if语句中，总的比较次数为：算法中的比较次数与n个关键字的值无关，因此最坏情形和平均情形的比较总次数相同。因此，算法是O(n2)阶的。空间代价只额外占用了几个工作单元，因此，它是个原址排序算法。

84.讨论：

算法SelectSort按比较次数计算的最好情形时间复杂度为：如果把关键字的移动作为基本操作，情况有所不同。从算法中的if语句可看出，关键字移动min=L[j]的次数可能少于比较min>L[j]的执行次数。另外，函数Swap()需要3次移动，共3(n–1)次。因此，选择排序算法的平均移动次数会比较小，而最好情形则为3(n–1)。当数据记录比较大时，移动代价大于比较代价，选择排序也可能有较好的性能。92.2.2插入排序（InsertionSorting）

1.插入排序的思路：与选择排序不同，它是从无序部分不经选择，任取一元，然后插入到有序部分的正确位置上。其步骤为：L[1..n]分为两部分：L[1..i]为有序部分，L[i+1..n]为未排序部分。1°i=1；2°把L[i+1]插入到L[1..i]中的正确位置，i++；3°if(i<n)goto2°；4°停止。2.算法的描述：算法2.2插入排序算法InsertSort103.算法的分析：最坏情形：最好情形：平均情形：设输入序列满足两个条件：1°n个关键字值是不同的，这可以简化分析；2°n个元素的所有不同的排列具有等可能性。在把L[i]插入到有序的L[1..i–1]的过程中，共有i种可能的位置，由假设2°可知落入每个位置的概率为1/i。而这i种情形所需要的比较次数分别为1，2，…，i-2，i-1，i-1，因此期望的比较次数为：11因此，

插入排序虽然也是O(n2)阶的算法，但在一般情形下，会比选择排序块。算法的空间代价：基本上不需要额外空间，也是一种原址排序算法。它也是稳定的。124.讨论：在基于相邻元比较交换的排序算法中，InsertSort是最优的。如果把数据的移动作为基本操作，每一次数据比较都有一次数据移动与之对应。因此，除了在外循环的n–1次移动之外，数据比较与移动次数是一致的，这与SelectSort算法是不同的。2.2.3起泡排序（BubbleSorting）

算法2.3起泡排序算法BubbleSort

算法BubbleSort的比较次数是确定的：移动次数与数据比较相对应，交换函数Swap需要三次数据移动，在最坏情形下是比较次数的三倍，而在最好情形下不需要移动。13BubbleSort是稳定的、原址排序算法。BubbleSort的一种实用改进算法是在程序中设一标记位，当一遍扫描中没有交换发生，则排序停止。算法2.4起泡排序的改进算法BSort

算法BSort的比较次数有所改进：142.3基于相邻元比较的排序算法和

希尔（Shell）排序

2.3.1插入排序的最优性定理2.1基于相邻元的比较及交换的排序算法1°在最坏情形下，至少需要n(n-1)/2次比较，即W(n)=Ω(n2)；2°在平均情形下，至少需要n(n-1)/4次比较，即A(n)=Ω(n2)。把n个元素排列问题归结为以n个关键字1,2,…,n的任一排列π：π(1),π(2),…,π(n)作为输入，排序过程就是消灭序列中的逆序的过程。所谓逆序（Inversion）（π(i),π(j)），即i<j且π(i)>π(j)。例如序列（2，4，1，5，3）有4个逆序：（2，1），（4，1），（4，3），（5，3）；15证明的关键是，在序列中，如果两个相邻元为一逆序，经过交换肯定消除了这个逆序，但这一交换只能消灭这一个逆序。证明：1°存在一种排列：n,n-1,…,2,1为全逆序，共包含n(n-1)/2个逆序，故在最坏情形，任一依靠相邻元比较、交换完成的排序过程，至少需n(n-1)/2次比较，即W(n)=Ω(n2)。2°对于平均情形，实际上需要计算1,2,…,n的所有不同排列的平均逆序数。当n>1时，任一排列π，必有一个唯一的、不同于它的对偶排列；π’是π的对偶排列，即π’是π的反序：π’(1)=π(n)，π’(2)=π(n-1),…,π’(n)=π(1)，例如，(2,4,1,5,3)的对偶排列是(3,5,1,4,2)；1～n之间的任一整数对（i,j）（i≠j）如果是逆序，必然出现在任一排列π及其对偶排列π’二者之一；161～n之间共有不同的整数对（i,j）n(n-1)/2个；1,…,n的所有排列是成对出现的，故每一排列平均有n(n-1)/4个逆序，平均至少需n(n-1)/4次比较，即A(n)=Ω(n2)。由定理知：1°算法InsertSort和BSort在上述条件下是最优的；2°为了设计比θ(n2)阶更快的排序算法，数据的比较和移动必须在间隔较大的元素之间进行。2.3.2希尔（Shell）排序

该排序算法首先把输入序列分成h个间距为h的子序列，对每个子序列进行h–sorting。例如，取h=6，则L[1..n]分为6个子序列：17L[1],L[7],L[13],…L[2],L[8],L[14],…L[3],L[9],L[15],…L[4],L[10],L[16],…L[5],L[11],L[17],…L[6],L[12],L[18],…进行h–sorting后，就是逐步减少h的大小，直至把h减少到1，完成排序工作。在最后一次h=1时，采用InsertSort或BSort算法，可能出现最好情形或几乎最好情形，而InsertSort的B(n)=n-1，故总比较次数有望缩小。Shell排序算法有几个因素可以有大的变化：第一个h值如何取，h值如何逐步减少到1每次h–sorting采用何种算法，都对整个算法性能有大的影响。18Shell排序算法：输入：KeyL[1..n]：关键字数组；inth[1..t]：递增整数序列，h[1]=1；算法2.5希尔排序算法ShellSort当t=1时，ShellSort退化为InsertSort。增量序列ht,ht-1,…h1=1应事先确定，一个较好的选择是：h1=1,hs+1=3hs+1其中1≤s≤t使ht+1<n，ht+2≥n。当n比较大时，Shell排序比插入排序要快，因为当ht>1时，在h-sort过程中，一次比较和交换可以至多消除2ht-3个逆序。关于Shell排序的研究至今仍在继续，因为对于已知的n，怎样的增量h序列使算法性能最佳，其最优时间复杂度如何，目前尚不清楚。一些比较好的成果指出，适当选取增量序列，Shell排序算法的复杂度可以达到O(nlog2n)和O(n1.25)。192.4O(nlogn)阶的排序算法

2.4.1快速排序算法QuickSort

1.算法的思路：其关键操作是划分（partition）：取n元中的任一元（例如首元）作为划分元（pivot），令其余n–1个元与划分元经过比较，把较小者移至划分元左边，而较大者置于划分元之右，形成两个序列。左序列的所有元都小于划分元，右序列都不小于划分元，然后用同样的方法对左、右序列排序，从而完成排序目标。如Fig.2.1所示。划分过程中，划分元被放置到了排序过程的最终位置，其左、右两个序列虽然是无序的，但作为整体却被确定了位置，因此在完成左、右子序列的排序之后，整个排序过程也就完成。20212.算法QuickSort：

输入：未排序的L[1..n]，为了方便写递归程序可表示为L[first..last]。输出：已排序的L[first..last]。算法2.6快速排序算法QuickSort3.划分算法Partition：

QuickSort的核心是Partition。划分过程中，元素在数组中有较大幅度的移动，因此，这也是快速排序速度较快的内在原因。有各种不同的划分算法，其性能也不尽相同。一种较好的划分算法，其思想如Fig.2.2所示。2223程序开始，指针left=first，指向空位，即划分元pivot的位置，指针right=last，指向最右元，序列L[2..n]全为未做划分处理部分；首先自right开始，向左扫描，找到第一个小于pivot的元素，把它送往left指向的左空位，left右移一位；然后从left向右扫描，找到第一个不小于pivot的元素，把它送到right指向的位置（右空位），right左移一位，完成划分的一次循环。重复上述循环，直到left=right，令L[left]=pivot，返回left。算法2.7快速排序的划分算法Partition24划分过程中的实例：

254.QuickSort的复杂度分析：

最坏情形的总比较次数为：平均时间性能分析：首先假设：1°n个元素的关键字值互不相等。2°n个元素的关键字的所有不同排列，以等可能即相等的概率出现在输入序列中，因此，划分元的最终位置i也以相等概率分别取值为1,…,n。QuickSort的平均比较次数A(n)应满足递归方程：

26可简化为： （公式2.4.1）在最好情形时划分元总是处于序列的中间，递归方程可大致简化成：27定理2.2在输入序列的所有排列具有等可能性的条件下，算法QuickSort的平均数据比较次数为:其中c>0为一常数。证明方法1：采用归纳法

当n=1时，A(n)=0，cnlnn=0，命题成立；假设当1≤k＜n，A(K)≤cklnk成立；由公式2.4.1和假设得：

根据积分的性质：28于是，当n＞1取c=2时，A(n)≤2nlnn成立。推论2.3在输入序列的不同排序均匀分布的假设条件下，算法QuickSort的平均数据比较次数为:

证明方法2：为了简化关于A(n)的递归方程，由

29推出：为了消除过多的A(i)项，计算nA(n)-(n-1)A(n-1)：即 令 则有：30这是一个较为简单的递归方程，不难得到：由Harmonic级数， 为Euler常数，

，得：31

由此可以得到A(n)的更准确的表达式：5.空间复杂度分析：

单从划分算法来看，QuickSort除有限的工作单元外，不占用额外的空间，但在递归过程中，待排序段的首元和尾元下标需要保存，在最坏情形可能递归n–1次。因此，QuickSort在最坏情形下需要的空间代价为S(n)=θ(n)。326.关于QuickSort算法的几点讨论：

1）在最重要的性能，即平均时间代价上优于其它算法。当n比较大时，一般运行确实很快，因此被广泛采用。2）改善划分元的选取，可能产生更好的效果。常见的几种划分元的选取方法是：

·在first,…,last中取随机数i，以L[i]代替L[1]；

·

在first,…,last中，取中间值i=int((first+last)/2)；

·

取first，last，int（（first+last）/2）三者的中值为划分元下标。3）算法的核心是划分。不同的划分策略会影响到移动次数。4）QuickSort采用递归算法的形式，简明但运行时在时间和空间上开销较大。一种改进方法是使用由用户设计的栈取代递归。算法2.8快速排序的改进算法QStackSort

335）空间复杂度的改进：快速排序算法的额外空间需求与递归和栈有关。当把两次递归调用改为单侧进栈，可以改进空间复杂度。当输入为升序（已排序）时，共需n–1次进栈，占用O(n)空间。如果在程序中，每进行一次划分以后，就对[f,i-1],[i+1,l]两段进行比较，把较大的一半进栈，先计算（划分）较小的一半，其内层循环次数（即栈的长度）必然小于logn，因此空间代价可降为O(logn)。6）快速排序算法对于较小的n，其性能不及插入算法。因此，可以设计一种综合算法，当输入序列长度小于某个固定值（例如n0=50）时，改用InsertSort进行排序。7）快速排序的最坏情形时间复杂度和额外空间代价，无论如何改进，总是它的缺点和不足。342.4.2合并排序算法MergeSort

1.算法的思路：

把序列分为两部分，分别递归（排序）后，再把两个有序序列合并为一个有序序列。如Fig.2.4。352.有序序列的合并算法：

算法2.9有序序列的合并算法Merge

3.合并排序算法MergeSort：算法2.10合并排序算法MergeSort

4.算法的复杂度分析：

该算法对两个长度为m的有序序列的合并，在最坏情形下至少需要2m–1次比较。算法在最坏情形下的比较次数可用递归方程表示： （公式2.4.2）36忽略n为奇数的情形，由主项定理可得 。假定n=2k（k为正整数），则公式2.4.2可以简化为：直接推导得：该算法平均情形比较次数A(n)=Ω(nlogn)。其空间代价较大，需要大小为O(n)的额外空间。该算法是不稳定的。375.关于合并排序算法的讨论：

1）对于时间复杂度而言，在最坏情形下大大优于快速排序，但在平均情况下不一定优于快速排序。数据的移动次数也会对时间性能有所影响。2）可以比较容易地改写成非递归程序。3）合并排序的一种改进方法是充分利用输入序列中可能的已排序部分。算法2.11合并排序改进算法IIMergeSort2

例如，输入序列为（4，12，8，6，0，11，27，5，20），实际上是4个有序串：（4，12），（8），（6，，11，27），（5，20）。第一趟扫描合并为：（4，8，12），（5，6，9，11，20，27），第二趟扫描就已排好序。这个算法在在最好情形下的比较次数为B(n)=n–1。384）主要缺点是空间代价较大，每次合并操作都需要与待合并的数据等长的额外空间，其额外空间代价为O(n)阶。

5）适合于并行计算。2.4.3堆排序算法HeapSort

1.堆排序算法的思路：

如Fig.2.5，算法把待排序的数组L[1..n]视为一个二叉树，数组元素依次按广度第一的顺序与二叉树的结点相对应。结点间的链接利用下标来计算。对于结点i，如果2i>n，则i为叶结点，否则，2i为其左儿子下标，2i+1为其右儿子下标。39这样的二叉树的所有的叶结点位于树的最底层即d层或d–1层，在最底层的叶结点位于左端。算法由两部分组成，第一部分称为建堆（BuildingHeap），就是通过数据的比较和移动，使得二叉树上每个内部节点的值大于其左、右子结点的值。这样的二叉树称为堆（Heap），如Fig.2.6所示。40第二部分称为根删除—堆修复（Delete–Fix）过程，如Fig.2.7，可以描述为：for(i=n;i>=2;i--){Swap(L[1],L[i]);FixHeap(L[1..i-1]);}堆的修复过程，就是每次把两个儿子中的较大者上升，直到元素L[i]降到适当的位置为止。这一Delete–Fix过程至多重复n次，每次修复所需的比较次数不会大于树高，而平衡二叉树的高不会大于logn（n为结点数），故此算法应有较好的性能。2.算法的描述：

算法2.12堆排序算法HeapSort

41423.算法的分析：

令n'=2d–1且n'/2≤n≤n'，并把建堆过程写成递归形式：voidBHeap(H){BHeap(Hleft);BHeap(Hright);FixHeap(L,n,root,L[root]);return;}它与函数BuildHeap是等价的。由于FixHeap(L,n',root,L[root])的比较次数为2logn'，故有：43根据主项定理：因为b=2，c=2，取ε=0.1，有

故

因此，建堆过程在最坏情形下的时间复杂度为线性阶。对于算法的第二部分，因为对于有k个结点的堆进行修复，至多需要 次比较，即全部比较次数至多为：

44定理2.4

HeapSort在最坏情形下的数据比较次数为W(n)=2nlogn+O(n)，即HeapSort是一个θ(nlogn)阶的排序算法。HeapSort在平均情形下的比较次数是O(nlogn)。它是一个原址排序算法。4.堆排序算法的缺点：

1）当输入序列为有序或几乎有序时，堆排序算法根本没有利用序列有序的条件，需要θ(nlogn)次比较，与最坏情形相比几乎没有改进。2）堆排序大约需要2*nlogn次比较，在大多数情况下，比快速排序和合并排序要慢。5.加速堆排序算法AHeapSort：

在原来的FixHeap算法中，每一次需要做两次比较，即：if(L[vac*2]<L[vac*2+1])和if(k<L[larger])。改进后的AFixHeap算法，每一步只做一次比较。45算法2.13改进的堆恢复过程AfixHeap

在大多数情况下，第一个循环把空位移至叶结点，共用logn次比较，而向上的移动次数则很少。结点的比较次数在最坏情形下仍为2logn，但在大多数情况下则接近（大于）logn。如Fig.2.9所示。46为了把最坏情形下的比较次数由2nlogn缩小到nlogn，进一步改进的思路描述如下：设堆的高度为 ，空位的移动分为下移和上移，每下移、上移一层需要一次比较。开始时空位在顶点，设待插入元素的最终应插入的位置在h层，0≤h≤H。1°m=H/2；2°空位下移m层，共用m次比较；3°if(L[vac/2]<k)goto5°；4°m/=2;goto2°；5°空位上移至最终位置，至多用m次比较。利用这一改进，AheapSort在最坏情形下的数据比较次数应为W(n)=nlogn+nloglogn+O(n)。476.另一种树排序算法：

如果排序时建成一个顶元最小的堆（如图Fig.2.10），根消除后很难修复（合并）为一个堆，这就是堆排序为什么要把最大元素放到堆顶的原因。

48有改进算法LheapSort，把数组L[1..n]视为一个被称为左完全2-3树（简称LECT树或L树）的树结构。实例：L[1..n]，n=23。

每次取不大于剩余元素数的2k-1个元素形成一个完全二叉树，因n=15+7+1，故n=23个元的数组唯一地与Fig.2.11的树结构对应。数组元素按深度优先的顺序排列。49对于下标为i的结点，i+1是其左子结点的下标，右子结点的下标则需要利用其右邻完全树的根下标r来计算，即(i+r+1)/2。例如，结点2的左子结点下标为3=2+1，该完全树的右子结点下标为6=（2+9+1）/2。这需要至多为logn的额外空间来保存各个完全子树的根下标，即保留24、9、2、1四个值。LHeapSort同样由两部分——建堆过程和删除—整理过程组成建堆过程之后，L[1..n]已经对应一个n=23结点的左完全2-3树，故L[1]已是最小元。前几步删除—整理过程如图：50515253

删去L[1]，空位置不动，由L[2..23]形成另一棵L树—LT2；

LT2已是一个堆，故不需整理，转至下一步删除—整理；

删去L[2]，由L[3..23]形成新的L树—LT3；

整理LT3称为堆，其过程与HeapSort的FixHeap过程类似。一个简单的实例：n=11，L[1..11]={8，4，7，2，3，9，6，1，10，11，5}。下图是LheapSort(L,n)的排序过程，其中1～11步是建堆过程，12～23步是删除—整理过程。54557.算法LHeapSort的分析：

1）最坏情形和平均情形：在最坏情形下的时间复杂度为W(n)=θ(nlogn)。LHeapSort在最坏情形、平均情形下的性能与HeapSort大致相同。已有的研究成果指出，LHeapSort在最坏情形下的移动次数约为1.5nlogn次。2）最好情形：

表2.1有序条件下的各种算法性能

当输入序列为有序时，LHeapSort极快，不同算法的实验数据如表：56LHeapSort在最好情形下的比较次数为B(n)=2n=O(n)，数据移动次数为0次，而HeapSort在最好情形下的复杂度为B(n)=θ(nlogn)，已有的研究结果认为是B(n)≥nlogn/2。3）当输入序列为几乎有序时，性能比其它排序算法要好。4）空间代价：LHeapSort在排序过程中需要一个长度为logn+1的整型数组，用于存放各个完全数的根的下标。572.5排序算法的时间复杂度下界

2.5.1判定树（DecisionTree）模型对于n=3，设三个关键字为a，b，c，可以用程序区分出六种可能的排列次序。它对应于Fig.2.13的判定树（程序）581°比较排序算法与图中的判定树是一致的；2°任一比较排序算法（对某一确定n值）都与一棵判定树相对应；3°判定树的全部外部结点对应于所有不同的排序结果。例如，n=3时，a，b，c的六种不同结果都应包含在判定树的外部结点中。从DT的根到一个叶结点的路长，即某条路上的内部结点数，也是算法运行所需要的比较次数。判定树DT的最长路长即为算法在最坏情形下的比较次数，平均路长（从根到所有叶结点路长的平均值）即为算法在平均情形下的比较次数。因此我们把对于算法在最坏情形下和期望的时间复杂度的计算变换为对于算法对应的判定树的最长路长和平均路长的计算。592.5.2最坏情形引理2.5判定树DT的叶结点数l与树的深度d有如下关系： l≤2d。引理2.6有l个叶结点的DT的深度为：引理2.7任意一棵n元判定树DT至少有n!个叶结点。定理2.8任何n元比较排序算法在最坏情形下的比较次数为：2.5.3平均情形判定树DT中，根到所有叶结点的路径之和称为DT的外部路长epl（externalpathlength），而epl/l就是平均路长，其中叶结点数l>n!。60引理2.9在所有具有l个叶结点的判定树中，若某棵树的epl最小，则这个DT的所有叶结点是平衡的，即它的叶结点之多分布在树的最下面两层。如Fig.2.14。证明：

设判定树有叶结点X位于k层，k<d–1。因DT有d层，故必有叶结点Z1，Z2在d层，其父结点Y在d–1层。

61对判定树DT做一小的调整，把叶结点Z1，Z2从父结点Y上摘下，挂到结点X上（如Fig.2.15）。显然它仍然是一个有l个叶结点的判定树DT’，但外部路长epl发生了变化。具体地说有三条路长发生了变化：在DT上，从根到X，Z1，Z2的三条路长为k+2d。在DT’上，从根到Z1，Z2，Y的三条路长为2(k+1)+d-1=2k+d+1。因k<d–1，所以2k+d+1<k+(d-1)+d+1=k+2d，得证。62引理2.10有l个叶结点的判定树DT的最小epl可表示为：1°l=2k，有上面引理可以断定，最佳DT为完全满二叉树，即叶结点全在底层，显然

epl=llogl，即为上式。2°若l≠2k，设DT深度为d，全部叶结点在d层和d–1层，如Fig.2.16所示。这时，因 ，因此有下面的定理：63定理2.11任何n元比较排序算法在平均情形下的比较次数至少为log(n!)，即A(n)≥log(n!)≈nlogn–1.443n证明：因任一n元比较排序算法的判定树的叶结点数l≤n!，且所以642.6排序算法的有关研究

比较排序算法的改进与分析基数排序（RadixSorting）

例如当元素关键字有三位十进制整数组成时，算法如Fig.2.17所示。外部排序算法粗排序（RoughlySorting）

并行排序（ParallelSorting）第二章完6566算法2.1选择排序算法SelectSorttemplate<classKey>voidSelectSort(KeyL[],intn){

inti,j,k;

for(i=1;i<n;i++){

for(j=i+1,k=i;j<=n;j++)

if(L[k]>L[j])k=j;Swap(L[i],L[k]);}

return;}返回67算法2.2插入排序算法InsertSort

template<classKey>voidInsertSort(KeyL[],intn){

inti,j;Keytemp;

for(i=2;i<=n;i++){

for(j=i-1,temp=L[i];j>0;j--){

if(L[j]>temp)L[j+1]=L[j];

else{L[j+1]=temp;break;}}}

return;}返回68算法2.3起泡排序算法BubbleSorttemplate<classKey>voidBubbleSort(KeyL[],intn){

inti,j;

for(i=1;i<n;i++){

for(j=n;j>i;j--)

if(L[j]<L[j-1])Swap(L[j],L[j-1]);}

return;}返回69算法2.4起泡排序的改进算法BSorttemplate<classKey>voidBSort(KeyL[],intn){

intp=1;inti,j;

for(i=1;(i<n)&&p;i++)for(j=n;j>i;j--){p=0;

if(L[j]<L[j-1]){p=1;Swap(L[j],L[j-1]);}}}

return;}返回70算法2.5希尔排序算法ShellSorttemplate<classKey>voidShellSort(KeyL[],intn,intt,inth[]){

for(inth=h[t],s=t;s>=1;s--,h=h[s])

for(intk=1;k<=h;k++)

for(inti=h+k;i<=n;i+=h){Keytemp=L[i];

intj=i–h;

while((L[j]>temp)&&(j>0)){L[j+h]=L[j];j-=h;}L[j+h]=temp;}

return;}返回71算法2.6快速排序算法QuickSorttemplate<classKey>voidQuickSort(KeyL[],intfirst,intlast){

if(first<last){

intsplit=Partition(L,first,last);QuickSort(L,first,split–1);QuickSort(L,split+1,last);}

return;}返回72算法2.7快速排序的划分算法Partitiontemplate<classKey>intPartition(KeyL[],intfirst,intlast){

intleft=first;intright=last;Keypivot=L[first];

while(left<right){

while(L[right]>=pivot)right--;L[left++]=L[right];

while(L[left]<pivot)left++;L[right--]=L[left];}L[left]=pivot;

returnleft;}返回73算法2.8快速排序的改进算法QStackSorttemplate<classKey>voidQStackSort(KeyL[],intn){

intf,l,i;stack.push(1,n);

while(!stack.empty){stack.pop(f,l);

while(f<l){i=Partition(L,f,l);Stack.push(i+1,l);l=i–1;}}

return;}返回74算法2.9有序序列的合并算法Mergetemplate<classKey>voidMerge(KeyS[],intl,intm,intr){KeyT[];

inti=l;intj=m+1;intk=l;

while((i<=m)&&(j<=r)){

if(S[i]<=S[j])T[k++]=S[i++];

elseT[k++]=S[j++];}

if(i>m)

for(intp=j;p<=r;p++)T[k++]=S[p];else

for(intp=i;p<=m;p++)T[k++]=S[p];

for(p=l;p<=r;p++)S[p]=T[p];

return;}返回75算法2.10合并排序算法MergeSorttemplate<classKey>voidMergeSort(KeyL[],intfirst,intlast){

if(first<last){

intmid=(first+last)/2;MergeSort(L,first,mid);MergeSort(L,mid+1,last);Merge(L,first,mid,last);}

return;}返回76算法2.11合并排序改进算法IIMergeSort2template<classType>voidMergeSort2(TypeL[],intn){

while(n>1){

inti=1;intj,k;

do{

for(j=i;(j<n)&&(L[j]<L[j+1]);j++);

if(j==n)return;

for(k=j;(k<n)&&(L[k]<L[k+1]);k++);

if(k>j){Merge(L,i,j,k);i=k+1;}}

while(i<=n)}

return;}返回77算法2.12堆排序算法HeapSorttemplate<cla