《排序2010秋（数据结构word版课件）.doc》由会员分享，可在线阅读，更多相关《排序2010秋（数据结构word版课件）.doc（43页珍藏版）》请在三一文库上搜索。
1、第七章 排 序7.1 排序问题的基本概念在信息处理过程中最常用到的操作就是排序（sorting），也被称为分类，排序指按规定的顺序排列一个给定对象集合中的诸元素。现实生活中也有很多类似的例子，如图书管理员将书籍按分类号排序，以便查找，此外在电话簿、病历、档案以及其它任何需要查询物品的地方，都有需要排序的对象。在很多数据处理过程中，排序都是最基本操作之一。本章不涉及具体领域的数据处理，侧重介绍各类排序算法，使读者了解各类排序的特点和适用环境。同时，这些排序算法中使用了很多经典的计算机算法思想，非常有助于读者提高算法设计技巧。在讨论排序算法之前，先对问题进行形式化定义。给定待排序的n个项目R1，R
2、2，Rn称这些项目为记录，并称此n个记录的集合为一个文件，每个记录有一个关键词域K，其将决定最后的排序结果。上述n个记录相应的关键词分别是K1，K2，Kn在一个记录中，除关键词域外，还可能有许多其他信息。可以假定这些额外的“辅助信息”对于排序过程没有影响。在关键词域上定义一个次序关系“”，使得对于任意三个关键词的取值a、b、c，下列性质成立：(1) 在ab，a=b，ba 三个可能性中，有且只有一个可能性成立（三分率）；(2) 如果ab，并且bc，则有ac（传递性）。 这两个性质表达了线性次序的数学性质。任何记录集合，如果其关键词具有满足上述两个性质的关系“”，则这些记录可以按照本章给出的排序算
3、法进行排序。这种排序也称作“全序”。只满足性质(2)的排序，称为“半序”或“偏序”。在讨论排序算法之前，我们可以更清楚地来定义我们的问题，给定待排序的n个项目R1，R2，Rn我们称这些项目为记录，并称n个记录的整个集合为一个文件，每一个记录有一个关键词域K，它支配着排序的过程. 上述n个记录相应的关键词分别是K1，K2，Kn在一个记录中，除关键词域外，还可能有许多其他信息. 我们假定，这些额外的“辅助信息”对于排序过程没有影响.排序的目标就是寻找一个置换 使得诸关键词按照非递减的次序排列，即有 K(1)K(2)K(n) 我们如果进一步要求具有相同关键词的记录要保持它们原来的相对次序，即要求当K
4、(i)=K(j)并且ij时，总有(i)(j)，这里1i，jn，则我们就称该排序过程具有稳定性. 排序分为内排序和外排序当所有待排序的记录都在内存中时，我们称排序过程为内排序；当输入文件中的记录个数n大到计算机内存不能容纳时，排序过程必需借助外存来完成，这时的排序就称为外排序. 内排序在构造和存取数据方面具有更多的灵活性，而外排序要求我们应付比较严格的存取约束. 本章所提到的算法，对于待排序的记录都认为是一个序列R1，R2，Rn，其中Ri是当前序列的第i个位置，很多算法把该序列看成一维数组，此时Ri是数组的第i个元素。还有一些算法，把该序列看成一个链表，此时Ri是链表的第i个结点。排序算法很多，
5、在解决特定问题时应如何选择排序算法呢？首先应该从算法的时间代价和空间代价出发考虑（即应用环境中的CPU处理能力、存储容量等硬件约束和系统响应时间等处理效率要求），有些情况下也需要考虑算法实现的复杂程度（从软件工程角度考虑软件开发成本）。一般情况下以考虑时间代价为主。排序算法有多种分类方法。从元素的存储设备角度可分为内排序（在内存中进行）和外排序（在外存储器上进行）。按对关键词的操作可分为基于关键词比较的排序算法和分布排序算法。基于关键词比较的排序算法有插入排序（直接插入排序及Shell排序）、交换排序（冒泡排序及快速排序）、选择排序（直接选择和堆排序）、合并排序等。按时间代价分类，它们又可分为
6、两类：平方阶排序算法，它们一般都比较简单，特点是容易实现，但时间复杂度相对较高，最坏情况下时间复杂度一般为O(n2)；线性对数阶算法，以分治策略算法为主，最坏情况下时间复杂度一般为O(nlog(n). 分布排序算法不以关键词比较为基础，有较低的时间代价(即O(n)，但是需要对数据集有一定先验知识，比如数据分布于哪个区间内等。7.2 插入排序假设1jn，且记录R1，R2，Rj1已经排序，即有K1K2Kj1 。所谓插入，是将一个待排序的记录Rj插入到上述序列中的适当位置，使得新序列正好排序. 如果这个插入过程能够实现，那么我们就可以得到如下的排序算法：第一步：记录R1不用插入；第二步：K2与K1比
7、较，如果K2K1，则R2插入到R1的前面，否则R2就插入到R1后面； 第j步：记录Rj插到R1，R2，Rj1之中； 第n步，记录Rn插入到R1，R2，Rn1之中上述过程可由算法InsertSort来实现算法InsertSort ( R，n ) /* 直接插入排序算法，本算法排列n个记录，使得它们相应的关键词排列成一个非递减的序列 */IS1 逐一排序FOR j2 TO n DO ( ij1 / 每次循环将Rj插入到R1，Rj1之中 KKj . RRj . WHILE i0 AND KKi DO ( Ri+1Ri iil ) Ri+1R ) 算法InsertSort的每次FOR循环，正好完成了把
8、Rj插入到R1，R2，Rj1（此时K1K2Kj1）之中WHILE语句每次比较都要判断i是否大于零，为了减少在特殊情况下的比较次数，这里我们可引入一个虚设的记录K0，使K0min Ki | 1in算法InsertSortA ( R，s，e ) / 本算法将记录Rs，Rs+1，Re 排序已知Ks1min Ki | sieISA1 逐一排序FOR j=s+1 TO e DO ( ij1 . KKj RRj WHILE KKj，则称（Ki ，Kj）为上述序列的一个反序对. 实际上，正好是序列K1，K2，Kn的反序对个数. 我们设想K1，K2，Kn是这样生成的：第一次从 K1，K2，Kn 中选出一个元素
9、，不妨假定为最小元素K(1) ；第二次从 K(2) ， K(n) 选取一个元素，不妨假定为最小元素K(2) ，K(2)放在K(1)的左边或者右边，如放在左边则产生一个反序对，而放在右边不产生反序对；第三次从 K(3) ，K(n) 中选出一个元素，仍不妨假定为最小的元素K(3) ，K(3)可以放在K(1)和K(2)的左边、中间或者右边，并且由此产生的反序对的个数是2，l，0， 如果我们假设K(j)插人到K(1) ，K(2) ，K(j1)的每个位置的概率是相等的，即K(2)出现在K(1)左边或右边的概率是；K(3)出现在K(1)和K(2)左边、中间和右边的概率是； K(n)出现在K(1)，K(n1
10、)中间的任何位置的概率是 .则有反序对的平均个数=0+(0+1)+ (0+1+2)+ +(0+1+2+n1) =0+ =n(n1)/4即的期望值为n(n1)/4 . 另外，由算法 InsertSortA我们可以看到，在排序过程中记录的移动次数为（n l）（n1）+ .由上述分析，我们有如下的分析表格：表9.1比较次数记录移动次数最好n12n2平均最坏直接插入排序算法的优点是算法的执行过程相当清晰，并且书写容易它的缺点是期望复杂性为 . 以下我们将会看到一些好的排序算法，其期望复杂性为那么，直接插入排序算法是否可以进一步求精呢？一种改进的方法是对半插入法，对半插入排序的思想是：在插入 Ri时（这
11、时R1，R2，Ri1已经排序），取Ki/2 与Ki 进行比较，如果Ki Kj+1 THEN ( RjRj+1 ) 算法中关键词的比较次数为 . 我们对如下9个元素执行冒泡排序：07 09 02 16 08 05 12 13 14算法执行完第一次冒泡过程之后，记录序列变成如下：07 02 09 08 05 12 13 14 16按照算法BSort，下一次冒泡操作从第一个元素到第八个元素，记录序列变成如下：02 07 08 05 09 12 13 14 16最后一次记录交换发生在第四和第五个元素之间，事实上，下一次冒泡过程我们不必要从第一个元素检查到第七个元素，因为从第五个元素之后的所有元素已经排
12、序完毕，不需要再进行冒泡操作，因此下一次的冒泡循环到第四个元素就可以结束了，这样可以减少算法的关键词比较次数. 也就是说，通过分析算法BSort，我们得出结论：在每一趟的比较中，当比较结束后，如果发现从某个位置t开始，不再进行记录交换，即说明从Rt+1Rn已经排序（证明留作练习），从而下一趟的比较只要进行到位置t即可. 据此我们可以给出一种改进的冒泡排序算法. 算法Bubble ( R，n )Bubble1 终止位置初始化BOUND n Bubble2 冒泡过程WHILE BOUND0 AND BOUND1 DO (t 0 / t用来记录一趟冒泡最后记录交换的位置 FOR j1 TO BOUN
13、D-1 DO IF Kj Kj+1 THEN ( RjRj+1 . tj ) . BOUND t ) 图9.4 以图示方式形象直观地描述了冒泡排序算法的执行过程，其中“”表示一趟冒泡的结束位置. 第一趟第二趟第三趟第四趟第五趟第六趟第七趟第八趟第九趟排列由下至上1316161616161616161614131515151515151515121413141414141414141012141313131313131308101212121212121212030810111111111111110603081010101010101011060308090909090909051106030
14、8080808080815051106030707070707041505090603060606061604090507060305050501090407050505030404090107040404040403030207010202020202020207020201010101010101图9.4算法Bubble的执行实例算法Bubble的时间复杂性主要依赖于while语句的循环次数、关键词的比较次数和记录的交换次数. 为了便于讨论，我们假定记录序列R1，R2，Rn所对应的关键词序列A = K1，K2，Kn是序列1，2，n的一个排列，我们令bj（1 j n）表示位于j左边大于j的关
15、键词的个数，则序列 b1，b2，bn 称为A的反序表. 例如，对于如下的关键词序列A，我们可以很容易地计算其反序表. A = 07，02，09，01，16，04，15，05，11，06，03，08，10，12，14，13 对于元素05，b5表示序列中位于05左边大于05的元素的个数，本例中b5=4，A的反序表B=3，1，8，3，4，5，0，4，0，3，2，2，3，2，1，0 .进一步，参照图7.4，我们可以看出，第一趟冒泡结束后，相应于第一趟的排列，其反序表可由上述反序表求得. 定理7.1给出了算法Bubble中反序表变化的具体规则. 定理7.1 设 K1，K2，Kn 是序列 1，2，n 的一
16、个排列， b1，b2，bn 是对应的反序表. 如果算法Bubble的一趟冒泡把 K1, K2, Kn 改变为 K1, K2, Kn,那么从b1, b2, bn中把每个非零元素减1,就得到了相应的反序表b1,b2,bn . 证明：如果Kj（1 j n）的左边有大于Kj的元素，设Km = max Kt | 1 t Kj ，则由算法Bubble知，Rm一定会与Rj交换，且Rj左边的其它元素不能与Rj交换. 所以如果Kj（1 j n）的左边没有大于Kj的元素，即，则说明Rj左边的所有元素都小于Kj，从而一趟冒泡之后， Rj左边的任何元素都不与Rj交换（因为它们都小于Kj），所以仍然有 . 证毕. 推论
17、9.1 算法Bubble的冒泡趟数A = 1 + max b1，b2，bn ；倒序情况下不用加1记录交换次数B=；关键词的比较次数C=，其中Ci等于第i趟冒泡时的BOUND减1. 由算法InsertSortA的分析，B的分布是明显的. 而A和C的分布比较复杂，我们在这里就不再详细描述，有兴趣的读者可参阅其他文献. 下面的表格给出了冒泡排序算法的特征. 表9.2比较交换趟数最好n101平均最坏n改成n-1 直接插入排序和冒泡排序算法的比较：由节7.2中算法InsertSortA的分析表格7.1及上述表7.2可以看出. 算法Bubble需要更多的元素移动和较多的平均比较次数，而且实现算法Bubbl
18、e的技术和分析过程都比较复杂. 因此，除非待排序的序列几乎排序，否则我们是不会选用冒泡排序方法的. 这两种排序算法的期望复杂性都是，并且这两种排序方法都有一个特点，即对每个元素来说，只有当排序结束时，它才能进入正确的排序位置. 本节所述的冒泡排序算法是把最大的元素向后移，一趟冒泡，至少可以把关键词最大的记录送到最后位置（或最上边）；当然也可以倒过来做，把小的元素向前移或向下移，一趟冒泡，至少可以把关键词最小的记录送到最前面的位置（或最下边）. 气泡的下沉和上浮实质上没有什么区别，但是把下沉和上浮过程逐趟交替进行可以获得更好的效果. 举例如下：对于序列 35，88，16，27，32，4，90，5
19、6，79单纯的上浮排序算法过程如下：第一趟第二趟第三趟第四趟第五趟第六趟79909090909090567988888888889056797979797948856565656563243535353535273243232323216273242727278816272741616353516161644 下沉和上浮逐趟交替的排序算法过程如下： 初始 上浮 下沉 上浮 下沉第一趟第二趟第三趟第四趟79909090905679798888 90568879794885656563243235352732273232162716272788163516163535444算法的改善显而易见. 7
20、.3.2 快速排序分划交换排序为了加快排序的速度，C. A. R. Hoare于1962年提出了一种快速排序方法，该方法可以看成是插入排序的改进，其与插入方法不同之处在于：Hoare的快速排序方法把控制分划过程的关键词Kj直接放在它排序的最终位置上，而不是放在排序的子文件（ R1，R2，Rj-1 ）中的恰当位置. 这样，如果Kj放的最终位置为S(j)，则当i S(j) 时有Ki Ks(j) ；而当i S(j) 时，有Ki Ks(j) 该方法的主要思想是不断地交换反序对，那么通过交换反序对能否给出一种较快的排序算法呢？事实上是可能的，因为一对反序对的交换，对应交换了多个反序对（因为两个元素不一定
21、相邻），如何选择待交换的反序对，使得这两个元素交换后，反序对的数目减少的最多，成为此类算法的关键问题。快速排序算法给出了这样一种策略，该策略是说，虽然我们不能肯定某一次交换是最佳交换，但是经过一次分划之后，比R1大的元素都放在了R1的后面，比R1小的元素都放在了R1的前面. kmKm+1km+2KnKn+1开 始27990813648616710882590100ij第一次交换27990813648616710882590100ij第二次交换27250813648616710889990100ij第三次交换27250813108616764889990100ij扫 描 交 叉272508131
22、07168664889990100jiRm与Rj互换27250813107168664889990100ji分 划 表16250813107278664889990100 图9.5 算法QSort的分划实例按照上面的分析，如果Kj（相应于Rj）放在它的最终位置之后，原来的文件（R1，R2，Rn）就分划成两个子文件（R1，R2，Rs(j)1）和（Rs(j)+1，Rn）,并且这两个子文件可以单独进行排序当两个子文件都排序完成之后，整个文件也就完成了排序任务. 以下是分划交换排序的递归算法. 算法QSort（R，m，n）/ * Hoare快速排序的递归算法，该算法对文件（Rm，Rn）进行排序. 我们
23、选择Km作为控制分划的关键词，并假定对任意的min有KiKn+1 . */QSort1 递归出口IF m n THEN （ im . jn+1 . KKm . WHILE i j DO / 用Km 分划文件（Rm，Rn） （ ii+1 WHILE Ki K DO jj1 . IF i j THEN Ri Rj ) Rm Rj . QSort ( R，m，j1 ) . QSort ( R，j+1，n ) ) 图9.5给出了算法QSort的第一次分划过程. 利用数学归纳法很容易证明算法QSort的正确性，该证明留作习题. 为了分析算法QSort的时间复杂性我们规定关键词的比较为基本运算，同时为了方
24、便，我们不妨假定文件中的关键词互不相等. 定理7.2 如果规定关键词比较为基本运算，则算法QSort (1，n) 的期望复杂性为，最坏复杂性 . 由定理7.2的证明我们看到，当文件（R1，R2，Rn）完全排序时，算法QSort的计算时间最大. 上述分析说明，对于随机产生的文件而言，算法QSort的复杂度为，而且不希望待排序的文件已经基本排序。然而，实际中经常遇到已经基本排序的文件。为此，设想用一个随机函数来选择用于控制分划的记录。即在算法QSort的语句“im”之前插入语句“RmRrand (m, n)”，其中rand (m, n)是一个随机函数，且m rand (m, n) n . 上述做法
25、虽然能保证待分划文件的随机性，但这个过程（平均来看）大约产生多于(nm+1)/2个的随机数。因为随机数的产生很费时，故上述做法是不可行的。代替寻找随机数的方案是三者取中法，该方法对于基本排序的文件可产生大体上均等的两个子文件。具体实施的办法是在算法QSort的语句“im”之前增加如下的语句序列： . IF Km+1Kn THEN Rm+1Rn . IF KmKn THEN RmRn . IF Km+1Km THEN Rm+1Rm . 该过程保证Km是Km、K(m+n)/2和Kn的中间值，下面给出修改后的分划算法。算法Part（R, m, n. j） /* 三者取中值的分划算法，该算法对文件(R
26、m, , Rn)进行分划，算法结束后 Rj是控制分划的记录。假定Kn+1Kt ( m t n ) */ Part1. 选中间值元素 R(m+n)/2Rm+1 . IF Km+1Kn THEN Rm+1Rn . IF KmKn THEN RmRn . IF Km+1Km THEN Rm+1Rm . Part2. 分划开始 im jn+1 KKm . Part3. 用Km分划文件( Rm，Rm+1，Rn ) WHILE i j DO ( ii+1 WHILE Ki K DO jj1 . IF i j THEN RiRj ) RmRj 为了给出快速排序的非递归算法，需要一个辅助堆栈。该堆栈存储一些待
27、排序的子文件。算法的实现过程就是不断调用算法Part的过程。注意到算法Part所处理的文件，其长度应大于等于3；另外，当文件很小时，直接插入排序算法比算法 QSort的效率高，鉴于这两个原因，通常的作法是选定一个常数M（一般5M15），当文件长度大于等于M时就调用算法Part，否则就采用直接插入排序算法进行处理。算法 HSort ( n, R, M ) /* Hoare快速排序的非递归算法，变量 M已给定，5M15对文件(R1, R2, , Rn)进行排序 */HSort1. 堆栈初始化CREATS( S ) HSort2. 设置栈底元素S(0, 0) HSort3. 初始化f1 . tn .
28、 Kn+1+ . K0 .HSort4. 对长度大于或等于M的记录序列分划排序 WHILE ft DO ( Part ( R, f, t. j )/ 分划文件(R1, R2, , Rn) CASE DO ( jfM AND tjM : IF NOT(StackEmpty(s) THEN (f, t) S ELSE tf1. jfM AND tjM: fj+1 . jfM AND tjtj THEN ( S(f, j1) . fj+1 ) ELSE (S(j+1, t) . tj1) ) ) . HS5 插入排序InsertSortA( R, 1, n ) . 上述算法在分划文件时有四种可能，最
29、后一种情况是两个子文件的长度都大于等于M . 在这种情况下，算法HSort在栈S中存储的是较大的子文件。这样做的目的是为了最大限度地减少辅助堆栈S所占用的空间。算法HSort中的堆栈S可能包含的最大元素个数留作习题来推导。9.3选择排序选择排序的基本思想是：对等待排序的文件（R1，R2，Rn）进行n改成n-1次选择操作，其中第i次操作是选择第i小（或大）的记录放在第 i个（或n i + 1个）位置上. 9.3.1 直接选择排序 最简单、直观的选择排序方法如算法SSort所述，即第i次操作是在剩余的ni+1个记录中进行一趟比较，然后确定出第i大的记录并把它放在第ni+1个位置上. 算法 SSor
30、t（R，n） / 直接选择排序算法，该算法排序文件（R1，R2，Rn）SS1 排序FOR j=n TO 2 STEP 1 DO ( tl . FOR i2 TO j DO IF Kt Ki THEN ti / 找第j小元素的下标 RjRt ) / 将Rt放到第j个位置上 很明显，算法 SSort在找第 j小元素时，需要进行 j-1次关键词比较. 故算法 SSort的关键词比较总次数为（nl）+（n2）+ +1=n（n-l）（次）. 如下表格反映了算法SSort的时间复杂性. 关键比较次数记录交换次数所有情况n（nl）nl从上面的简单分析表格我们可以看到，不论对于何种输入，算法SSort的时间复杂性都为 . 9.3.2 堆排序堆的概念：完全二叉树中的任意结点的关键词大于等于它的两个儿子结点的关键词. 我们把这样的数据结构称为堆. 949375918544511848581034图9.9 包含12个元素的堆下面我们讨论使用堆的排序算法注意到在一个堆中，根结点对应的元素一定是最大元素. 而根结点的编号为1，故交换Rl和Rn之后，最大元素将进入正确的排序位置，但此时前n1个元素不再满足堆的特性.