07 第7章 排序.pptx

第1页：第七章排序封面

第七章排序

第2页：从数学和计算机角度而言

从数学和计算机角度而言，简单地说排序算法就是把元素按照一定的序关系列表，最常见的序关系是数字序和字典序。高效的排序算法有助于提高其他算法的效率，如查找算法。此外，在很多情况下，排序有助于规范化数据和便于人类阅读、理解。尽管排序问题本身相对于其他计算理论问题而言并不复杂，但要设计高效的、有针对性的排序算法也并非易事，因此针对它的研究一直在持续开展。

第3页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第4页：排序，也叫分类

排序，也叫分类，是将一组杂乱无章的数据按一定的规律排列起来的过程。文件，是待排序数据对象的集合；一个数据对象也叫作一个记录，记为R1，R2，…，Rn关键词域(key):通常数据对象由多个属性域(多个数据成员)组成，其中可将一个属性域作为排序依据，该域即为关键词域。关键词记为：K1，K2，…，Kn；排序：将记录按关键词域递增或递减的顺序排列7.1基本概念

第5页：每个文件用哪个属性域作为关键词

每个文件用哪个属性域作为关键词，要视具体的应用需要而定；即使是同一个文件表，在解决不同问题的场合也可能取不同的关键词域。主关键词:如果在数据表中各个对象的关键词互不相同，这种关键词即主关键词。按照主关键词排序，排序的结果是唯一的。次关键词:数据表中有些对象的关键词可能相同，这种关键词称为次关键词。按照次关键词排序，排序的结果可能不唯一。

第6页：排序算法的度量指标

排序算法的度量指标:排序的时间开销(排序算法的时间复杂性):是衡量算法好坏的最重要标志。可用算法执行中关键词的比较次数与数据的移动次数来衡量。各算法的时间复杂性一般都按平均情况进行估算。对那些受对象初始排列及对象个数影响较大的，需要按最好和最坏情况进行估算。算法的空间复杂性:主要考察排序过程所需辅助存储空间的大小。

排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]，它们的关键词k[i]=k[j]，且在排序之前对象r[i]排在r[j]前面，如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。

第7页：排序算法很多

排序算法很多，在解决特定问题时应如何选择排序算法呢？首先应该从算法的时间代价和空间代价出发考虑（即应用环境中的CPU处理能力、存储容量等硬件约束和系统响应时间等处理效率要求），有些情况下也需要考虑算法实现的复杂程度（从软件工程角度考虑软件开发成本）。一般情况下以考虑时间代价为主。

第8页：排序算法有多种分类方法

排序算法有多种分类方法:–从元素的存储设备角度可分为内排序（在内存中进行）和外排序（在外存储器上进行）。–按对关键词的操作可分为基于关键词比较的排序算法和分布排序算法。–按时间代价分类：平方阶排序算法，它们一般都比较简单，特点是容易实现，但时间复杂度相对较高，最坏情况下时间复杂度一般为O(n2)；线性对数阶算法，以分治策略算法为主，最坏情况下时间复杂度一般为O(nlog(n)).

第9页：第七章排序目录

第七章排序7.1基本概念7.2插入排序直接插入排序希尔排序7.3交换排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第10页：7.2 插入排序

10§7.2插入排序例：原有序表：(915232837)20找插入位置:(915^232837)20新有序表:(91520232837)插入排序思想基于插入操作所完成的排序。插入:将一个记录插入到已排好序的有序表中，从而得到一个新的记录数增一的有序表。

第11页：直接插入排序算法

117.2.1直接插入排序算法1.基本思想待排序记录R1，R2，…，Rn–1, Rn第一步：R1第二步：(R1),R2第三步：(R1, R2),R3……第j步：(R1，R2，…，Rj–1),Rj……第n步: (R1，R2，…，Rn–1),Rn．

第12页：一次插入过程

例：j=59152823081 2 3 4 5 616162816231616一次插入过程1616原有序表中关键词比Rj大的记录数：dj比较次数：dj+1移动次数：dj+2281623

第13页：算法InsertSort

132.算法描述算法InsertSort(R,n)FOR j＝2 TO n DO(

第14页：算法InsertSortA

算法InsertSortA( R, s, e )//引入虚拟记录,Ks-1≤min{Ki| s≤i≤e}ISA1 [逐一排序]FOR j＝s+1 TO e DO( i←j-1．K←Kj. R←Rj.WHILEK＜KiDO( Ri+1←Ri．i←i-1．)Ri+1←R．) ▌

第15页：算法InsertSortA（续）

FOR j＝s+1 TO e DO( i←j-1．K←Kj. R←Rj.WHILE K＜KiDO( Ri+1←Ri．i←i-l )．Ri+1←R )▌k[1]k[2]k[3]k[4]k[0]k[5]8724－∞6j[2467－∞8][8]724－∞62[278]4－∞64[78]24－∞63[2478]－∞65

第16页：算法分析

163.算法分析设dj是Rj左边关键词大于Kj的记录个数，则算法InsertSortA中关键词的比较次数为：记录的移动次数为

第17页：最好情况下

最好情况下，排序前记录已经按关键词从小到大有序排列，即dj=0。每趟只需与前面的有序部分的最后一个记录的关键词比较1次，记录移动2次，总的关键词比较次数为n-1，记录移动次数为2(n-1)。

第18页：最坏情况下

最坏情况下：第i趟时，第i个记录前面所有记录的关键词都比第i个记录的关键词大，即dj=j-1总的关键词比较次数：记录移动次数：

第19页：平均情况下

平均情况下，若待排序文件中记录所有可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和记录移动次数分别为因此，直接插入排序的时间复杂度为O(n2)。

第20页：平均情况下（续2）

平均情况下，考察分析的期望值。对于序列K1，K2，…，Kn，如果1≤i＜j≤n，且Ki>Kj，则称(Ki,Kj)为上述序列的一个反序对。实际上，正好是序列K1，K2，…，Kn的反序对个数。

第21页：有反序对的平均个数

则有反序对的平均个数= 0+ (0+1)/2+ (0+1+2)/3+ … +(0+1+2+…+n–1)/n= 0+1/2+2/2+ … +( n–1)/2= n(n–1)/4即的期望值为n(n–1)/4 .

第22页：

第23页：直接插入排序算法总结优点

234.直接插入排序算法总结优点:是算法的执行过程相当清晰，并且书写容易.缺点:期望复杂性为O(n2) .稳定性：直接插入排序是稳定的排序方法。最好情况是：当被排序文件初态为正序时，算法的时间复杂度为O(n) .辅助空间：O(1)

第24页：直接插入排序算法（续2）

245.直接插入排序算法是否可以进一步改进呢？直接插入排序算法中包含了一个查找过程，对前部已经排序完的记录执行顺序查找。这显然是其效率低下的原因之一，是否可以通过改进顺序查找来提高排序效率呢?

第25页：通过将顺序查找改为二分查找

通过将顺序查找改为二分查找，可以构造二分插入排序算法。即在插入第j个元素时，不是像直接插入排序那样顺序寻找插入的位置，而是采用对半（或二分）的方法插入。如果文件（R1，R2，…，Rn）采用顺序存储，则对半插入排序算法可以减少关键词的比较次数，但是记录的移动次数仍不能减少。如果文件（R1，R2，…，Rn）采用链接存储，不能使用对半的方法寻找插入位置。

第26页：第七章排序目录

第七章排序7.1基本概念7.2插入排序直接插入排序希尔排序7.3交换排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第27页：7.2 希尔

277.2.2希尔(shell)排序1、希尔排序（渐减增量排序法）思想：1959年DonaldL.Shell提出Shell排序法，源自对直接插入算法的改进.把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

第28页：将十个数进行希尔排序

28[例]将十个数进行希尔排序的示例。0 1 2 3 4 5 6 7 8 936 25 48 12 652543 58 76 32下标d1=5254348581276253632652525 48 12 32 36 43 58 76 65一趟排序结果

第29页：将十个数进行希尔排序（续2）

29[例]将十个数进行希尔排序的示例。0 1 2 3 4 5 6 7 8 9下标d2=22525 48 12 32 36 43 58 76 652548324376251236586532434812252512 32 25 43 36 48 58 76 65二趟排序结果122525 32 36 43 48 58 65 76三趟排序结果d3=1

第30页：希尔排序增量的取法

30●希尔排序增量的取法：d1= = =5∟n/2∟∟10/2∟d2= = =2∟d1/2∟∟5/2∟d3= = =1∟d2/2∟∟2/2∟

第31页：算法分析Shell算法

312、算法分析Shell算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。

第32页：Shell算法的性能

Shell算法的性能与所选取的分组长度序列有很大关系。前面介绍的实例是最简单的分组长度序列，即n/2i，最坏情况下时间复杂度为O(n2).一般实际应用中选择2.2作为递减因子效果更好，而不是2.如果选择2k-1为分组长度序列，最坏情况下能达到.

第33页：V.Pratt于1969年证明如下结论

V.Pratt于1969年证明如下结论：如果渐减增量序列取值为形如且小于n的所有自然数的集合（即），则Shell算法的时间复杂度为.

第34页：本节内容目录

Knuth利用大量的实验统计资料得出，当n很大时，关键词平均比较次数和记录平均移动次数大约在n1.25到1.6n1.25的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。不稳定的排序算法

第35页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序冒泡排序快速排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第36页：交换排序反序

367.3交换排序反序对：对于序列K1,K2,…,Kn,若1≤i<j≤n,且Ki>Kj,则称(Ki,Kj)为上述序列的一个反序对。交换排序的思想：交换文件中存在的反序对，直到不存在反序对为止。交换排序包括：冒泡排序、分划交换排序（快速排序）。

第37页：7.3.1 冒泡排序

377.3.1冒泡排序1、冒泡排序思想：通过比较相邻记录的关键词，交换存在逆序的记录；使关键词较大的记录如气泡一般逐渐往上“飘移”直至浮出“水面”。

第38页：7.3.1 冒泡排序（图）

i= 90902160805121 2 3 4 5 6 7 8 91314071 2 3 4 5 6 7 8 9090216080512131407i= 81 2 3 4 5 6 7 8 9090216080512131407

第39页：算法BSort

392、冒泡排序算法算法BSort ( R，n )BS1 [冒泡过程]FOR i=n TO 2 STEP–1 DOFOR j=1 TO i–1 DOIF Kj> Kj+1THEN ( Rj↔Rj+1).▌关键词的比较次数:(n-1)+(n-2)+…+1=(n-1)n/2

第40页：经过一趟冒泡

经过一趟冒泡，可以把具有最大关键词的记录移至最后（第n个位置）。第i趟冒泡，把第i大记录放在倒数第i(正数第n-i+1)个位置上。做n-1趟冒泡，就可以对所有记录排序。发生一次记录交换，反序对的个数减少一个。排序中可能出现如下情况：每趟比较中，在某位置后，没有记录交换；最后几趟没有交换。

第41页：经过一趟冒泡（图）

i= 90902160805121 2 3 4 5 6 7 8 91314071 2 3 4 5 6 7 8 9090216080512131407i= 81 2 3 4 5 6 7 8 9090216080512131407

第42页：算法Bubble

423、冒泡排序算法的改进算法Bubble(R，n)Bubble1[终止位置初始化]BOUND←n．//每趟冒泡关键词比较的终止位置Bubble2[冒泡过程]WHILEBOUND≠0DO(t←0．//每趟冒泡记录交换的最后位置FOR j＝1 TO BOUND−1 DOIF Kj> Kj+1THEN ( Rj↔Rj+1.t←j.)BOUND←t) . ▌

第43页：算法分析最好情形

434、算法分析最好情形：记录的初始排列按关键词从小到大排好序时，此算法只执行一趟起泡，做n-1次关键词比较，不发生记录交换；最坏情形：算法执行了n-1趟起泡，第i趟(1≤i<n)做了n-i次关键词比较，执行了n-i次记录交换,此时，总的关键词比较次数和记录交换次数为(n-1)n/2

第44页：一般情形假定记录序列

一般情形假定记录序列R1，R2，…，Rn所对应的关键词序列为A={K1，K2，…，Kn}令bj（1≤j≤n）表示A中关键词第j小的记录左边大于它的关键词的个数，则文件{b1，b2，…，bn}称为A的反序表.A={07,09,02,16,08,05,12,14,13}B={2,4,0,2,0,1,2,1,0}

第45页：经过一趟冒泡后

经过一趟冒泡后，记录的位置发生变化，反序表也发生变化。定理7.1设{K1，K2，…，Kn}是序列{1，2，…，n}的一个排列，{b1，b2，…，bn}是对应的反序表.如果算法Bubble的一趟冒泡把{K1,K2,…,Kn}改变为{K1′,K2′,…,Kn′},那么从b1,b2,…,bn中把每个非零元素减1,就得到了相应的反序表{b1′,b2′,…,bn′}.A={07, 09, 02, 16, 08, 05, 12, 14, 13}B={2, 4, 0, 2, 0, 1, 2, 1 , 0}A′={07, 02, 09, 08, 05, 12, 14, 13 ,16}B′={1, 3, 0, 1, 0, 0, 1, 0 , 0}

第46页：证明

证明：如果Kj（1≤j≤n）的左边有大于Kj的元素，设Km=max{Kt|1≤t<j并且Kt>Kj}，则由算法Bubble知，Rm一定会与Rj交换，且Rj左边的其它元素不能与Rj交换。所以如果Kj（1≤j≤n）的左边没有大于Kj的元素，则说明Rj左边的所有元素都小于Kj，从而一趟冒泡之后，Rj左边的任何元素都不与Rj交换（因为它们都小于Kj），所以仍然有.证毕。

▐

第47页：推论7.1

推论7.1算法Bubble的冒泡趟数A=1+max{b1，b2，…，bn}；记录交换次数B=∑nbi；关键词的比较次数C=∑ACi，其中Ci等于第i趟冒泡时的BOUND减1.A、B、C分布较为复杂，平均情形复杂度的计算较为复杂(略)；

第48页：改进的冒泡排序算法的复杂性

改进的冒泡排序算法的复杂性：

第49页：冒泡排序算法总结时间复杂度

495、冒泡排序算法总结时间复杂度：O(n2)（包括最坏和平均）.最好情况：当被排序文件初态为正序时，算法的时间复杂度为O(n) .稳定性：冒泡排序是稳定的排序方法。辅助存储空间：O(1) .为了进一步提高效率，可采用气泡上浮和下沉交替的方法。

第50页：第四趟第三趟第二趟第一

第四趟第三趟第二趟第一趟9090909079888879795679798856905656568843535324323232273227272716271616163516884443535

第51页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序冒泡排序快速排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第52页：7.3.2 分划交换排序

527.3.2分划交换排序1962年，Hoare提出了分划交换排序，也叫快速排序(QuickSort)。算法的出发点：1、通过交换反序对排序，一次记录交换使得文件中反序对的数目减少得最多;2、一趟分划把一个记录直接放在其最终的位置上。

第53页：快速排序的基本思想

531、快速排序的基本思想:任取待排序文件中的某个记录(例如取第一个记录)作为基准，按照该记录的关键词大小，将整个文件分划为左右两个子文件：–左侧子文件中所有记录的关键词都小于或等于基准记录的关键词–右侧子文件中所有记录的关键词都大于基准记录的关键词基准记录排在两个子文件中间。分别对两个子文件重复上述方法，直到所有记录都排在相应位置上为止。

第54页：快速排序算法描述

542、快速排序算法描述QuickSort ( R ) {if (R的长度大于1) {将文件R分划为两个子文件LeftR和RightR;QuickSort ( LeftR );QuickSort ( RightR );将两个子文件LeftR和RightR合并为一个文件R;}}

第55页：第一个大于

55(1) (2) (3) (4) (5) (6) (7) (8)(9)707369 23 93 18 1168100i(第一个大于)(第一个小于) j706869 2393181173100706869 2311189373100706869 231118937310018 68 69 23 117093 73 100

第56页：算法QSort

算法QSort(R,m,n)//Hoare快速排序的递归算法QSort1[递归出口]//Rm为基准记录，Rn+1关键词最大IF(m<n)THEN(i←m.j←n+1.K←Km.WHILEi<jDO(i←i+1．WHILEKi<KDOi←i+1.j←j–1.WHILEKj>KDOj←j–1.IFi＜jTHENRi↔Rj．)Rm↔Rj.QSort(R,m,j–1).QSort(R,j+1,n).)▌

第57页：快速排序

57(1) (2) (3) (4) (5) (6) (7) (8) (9)7073 69 23 93 18 11 68100i=1j=9i=2706869 23 93 18 1173 100j=870686923 93 18 1173 100i=3j=87068692393 18 1173100i=4j=8706869 239318 1173 100i=5j=8706869 2393181173100i=5j=7706869 2311189373100i=5j=7706869 23 111893 73100i=7j=6[186869 23 11]70[93 73] 100WHILEi<jDO(i←i+1．WHILEKi<KDOi←i+1.j←j–1.WHILEKj>KDOj←j–1.IFi＜jTHENRi↔Rj．)Rm↔Rj.快速排序一次分划过程示例:

第58页：一趟结果

58[18 6869 23 11]70[93 73]j=6一趟结果11 18[68 23]697073 93j=5三趟结果[11 18 23 68 69 70 73 93]最终结果多趟快速排序过程示例11 18[23]68 69707393四趟结果j=4[11]18[69 23 68]70[73] 93j=2二趟结果j=8

第59页：最终结果

59[18 6869 23 11]70[93 73]j=6[11]18[69 23 68]70[93 73]j=211 18[68 23]6970[93 73]j=5[11 18 23 68 69 70 73 93]最终结果11 18[23]686970[73]93j=8j=4算法QSort(R，m，n)IFm<nTHEN(i←m.j←n+1.K←Km.QSort1；

//一次分划程序段QSort ( R，m，j–1 ) .L1:QSort(R，j+1，n).L2:)▌

第60页：算法分析算法Qsort是递归的算法

603、算法分析算法Qsort是递归的算法，其递归树如图所示。一个结点表示一次递归调用。快速排序的趟数取决于递归树的深度。每次分划后，基准记录的左右子序列长度相同，是最理想的情况。7093731869682311

第61页：一次分划过程

61(1) (2) (3) (4) (5) (6) (7) (8) (9)7073 69 23 93 18 11 68100i=1j=9i=2706869 23 93 18 1173 100j=870686923 93 18 1173 100i=3j=87068692393 18 1173100i=4j=8706869 239318 1173 100i=5j=8706869 2393181173100i=5j=7706869 2311189373100i=5j=7706869 23 111893 73100i=7j=6[186869 23 11]70[93 73] 100一次分划过程(R,m,n)，有两个记录与基准记录比较两次，其余的记录和基准记录各比较一次。

关键词的比较次数为n-m+2。

第62页：个记录排序所需时间

设T(n)是n个记录排序所需时间。最好情况，每次分划后，都得到长度相等的两个子序列。总的计算时间为：由于，f(n) =O(n),即f(n)≤cn,T(n)≤cn+ 2T(n/2)

第63页：常数

T(n)≤cn+2T(n/2)//c是一个常数≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)≤2cn+4(cn/4+2T(n/8))=3cn+8T(n/8)………≤cnlog2n+nT(1)=O(nlog2n)可以证明,Qsort的平均计算时间也是O(nlog2n)。就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。

第64页：最坏情况

最坏情况:即待排序记录已按关键词由小到大(或由大到小)排好序，其递归树为单支树，每次分划只得到比上次少一个记录的子序列。此时，排序共需n-1趟，且第i趟需要n-i＋2次关键词比较，总关键词比较次数为：(n+1)+n+…+3=(n-1)(n+4)/2此时，排序速度退化到简单排序的水平。若能更合理地选择基准记录，使得每次分划所得两个子文件的记录数尽可能接近，可以加快排序速度。

第65页：定理7.2

定理7.2如果规定关键词比较为基本运算，则算法QSort(1,n)的期望复杂性为O(nlog2n)，最坏复杂性Wn=1/2n2+3/2n-2.为产生随机文件，可以采用两种方法：1.用一个随机函数选择用于控制分划的记录，但随机数的产生也很费时。2.三者取中法，每个待排序记录序列的第一个记录、最后一个记录和位置接近正中的3个记录，取其关键词居中者为基准记录。

即令Km是Km、K⌊(m+n)/2⌋和Kn的中间值。

第66页：算法Part

算法Part(R，m，n．j)//三者取中法的一次分划过程Part1[选中间值元素]R⌊(m+n)/2⌋↔Rm+1.IFKm+1>KnTHENRm+1↔Rn.IFKm>KnTHENRm↔Rn.IFKm+1>KmTHENRm+1↔Rm.Part2[分划开始]i←m．j←n+1．K←Km.Part3[用Km分划文件(Rm，Rm+1，…，Rn)]WHILEi＜jDO(i←i＋1．WHILEKi＜KDOi←i＋1．j←j–1．WHILEKj＞KDOj←j–1.IFi<jTHENRi↔Rj)．Rm↔Rj．▌

第67页：快速排序算法总结时间复杂度

674、快速排序算法总结时间复杂度: O(n2)//最坏.时间复杂度: O(nlog2n)

第68页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序直接选择排序堆排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第69页：7.4 选择排序思想

697.4选择排序思想：对待排序的文件进行n次选择操作，其中第i次选择第i小(或大)的记录放在第i(或n-i+1，倒数第i)的位置上。直接选择排序、堆排序

第70页：直接选择排序

707.4.1直接选择排序1、直接选择排序思想：选择第i（i= 1,2, …,n-1）大的记录的具体办法：在剩余的n-i+1个记录中进行一趟比较，确定出第i大记录，放在第n-i+1位置上。17 78 6 54 34 3817 38 6 54 347817 38 6 345478

第71页：直接选择排序算法

712、直接选择排序算法算法SSort (R, n)//待排序文件(R1,R2,…,Rn)SS1[排序]FORj=nTO2STEP–1DO(//从1到j找最大元素的下标tt←1.FORi＝2TOjDOIF Kt<KiTHENt←i．Rj↔Rt)．▌//将Rt放到第j个位置上

第72页：初始序列

72(1) (2) (3) (4) (5) (6)i t[212549 25* 16 08]2 1初始序列2算法SSort（R，n）FORj=nTO2STEP-1DO(t←1.FORi＝2TOnDOIFKt<KiTHENt←i．Ri↔Rt)▐[21254925* 16 08]3 2[21 254925*16 08]4 3[21 254925*1608]5 3[21 254925* 1608]6 3[21 25 08 25* 16]49[21250825* 1649][21 254925* 1608]一趟直接选择排序过程示例

第73页：多趟直接选择排序

多趟直接选择排序过程示例(1) (2) (3) (4) (5) (6)it1 [21250825*16]4922[21 160825*]254943[21 16 08]25*25 4915[08]162125* 2549[21254925*16 08] 3初始序列4[08 16]2125*25 492

第74页：算法分析直接选择排序

743、算法分析直接选择排序的关键词比较次数与记录的初始排列无关。假定整个待排序文件有n个记录，则第i趟选择所需的比较次数是n-i次。总的关键词比较次数为(n-1)+(n-2)+…+1= (n-1)n/2记录交换次数是选择的趟数: n-1.

第75页：直接选择排序算法总结时间复杂度

754、直接选择排序算法总结时间复杂度:O(n2)（包括最好、最坏和平均）.稳定性：不稳定的排序方法。辅助空间：O(1) .优点：简单、书写容易

第76页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序直接选择排序堆排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第77页：7.4.2 堆排序

777.4.2堆排序1、堆排序的原理选择排序的关键：找最大记录堆排序：利用淘汰赛的方式寻找当前序列中的最大记录淘汰赛的思想：对n个选手，两两比赛，得到⌈n/2⌉个优胜者，作为第一轮的结果；然后对这⌈n/2⌉个选手，再两两比赛，…，如此重复，直到选出一个冠军。

第78页：堆的定义完全二叉树中

782、堆的定义完全二叉树中的任意结点的关键词大于等于它的两个儿子结点的关键词。我们把这样的数据结构称为堆(极大堆)。极大(大根)堆极小(小根)堆

第79页：堆的定义完全二叉树中（图）

79949375918544511848581034[例]1 2 3 4 5 6 7 8 9 10 11 1294 93 75 91 85 44 51 18 48 58 10 34

第80页：堆的定义完全二叉树

堆的定义完全二叉树的数组表示Ki≤K2i&&Ki≤K2i+1完全二叉树的数组表示Ki≥K2i&&Ki≥K2i+1

第81页：堆排序算法设数组R存放堆

813、堆排序算法设数组R存放堆，则R[1]是关键词最大的记录，将R[1]和R[n]互换，使得最大记录放在R[n]的位置。调整R[1]，……，R[n-1]，使之成为新堆，则R[1]是其中最大者，再交换R[1]与R[n-1]，使R[n-1]中放入次最大记录。再对R[1]，R[2]，……，R[n-2]调整，使之成为新堆，再进行类似的交换，上述操作反复进行，直到调整范围只剩下一个记录R[1]为止。

此时，R[1]是n个记录中最小的，且数组R[n]中的记录已经按从小到大排列了。

第82页：堆排序算法的粗略描述

堆排序算法的粗略描述：（l）建立包含Kl，K2，…，Kn的堆；（2）FORi＝nTO2STEP–1DO（R1↔Ri．重建包含K1，K2，…，Ki–1的堆．）▌需解决的两个问题：①如何建堆②如何调整新堆

第83页：问题

问题②——重建堆：R1与Ri交换后，只有R1与其左右儿子不满足堆的性质。13884223241605914288912324160513884223241605428891232416058813422324160542889123241605881342232416054288912324160588244223131605428891232416058824422313160591

第84页：算法Restore

重建堆算法算法Restore(R，f，e)R1[初始化]j←f．R2[建堆]WHILEj≤⌊e/2⌋DO//判断j是否为内结点(IF(2j<e)AND(K2j<K2j＋1)//m为j的最大子结点THENm←2j+1.ELSEm←2j.IFKm>KjTHEN（Rm↔Rj.j←m.）ELSEj←e.）▌重建堆算法的时间复杂度为O(log2n)

第85页：问题（续2）

问题①——初始建堆:将以序号⌊n/2⌋，⌊n/2⌋－1 ,…, 1的结点为根的子树都调整为堆即可。[例]关键词序列（42,13,91,23,24,16,05,88)。4213912324160588

第86页：堆排序算法

堆排序算法算法HeapSort(R，n)HS1[初始建堆]FORi＝⌊n／2⌋TO1STEP–1DORestore（R，i，n）．HS2[排序]FORi＝nTO2STEP–1DO(R1↔Ri.Restore(R，1，i–1)．)▌

第87页：堆排序过程关键字序列

堆排序过程关键字序列(42,13,91,23,24,16,05,88)42889123241605139188422324160513428891232416051388244223131605911、建立初始堆2、交换，并重建堆

第88页：堆排序过程关键字序列（图）

8842889123241605134224162313058891428891232416051324231605134288914288912324160513231316052442889142889123241605131613052324428891

第89页：堆排序过程关键字序列（续2）

894288912324160513130516232442889142889123241605130513162324428891

第90页：堆排序算法总结时间复杂度

904、堆排序算法总结时间复杂度:最好、最坏和平均情况相同重建堆算法为O(log2n)堆排序算法为O(nlog2n) .稳定性：堆排序是不稳定的排序方法。辅助存储空间：O(1) .

第91页：交换

91492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 1649交换0号与5号对象,5号对象就位初始最大堆

第92页：交换（续2）

922525*082116490123451625*0825214902543125 25* 21 08 164916 25* 21 0825492525*082116490123451625*0825214902543125 25* 21 08 164916 25* 21 082549交换0号与4号对象,4号对象就位从0号到4号重新调整为最大堆

第93页：交换（续2）

9325*1608212549012345081625*25214902543125* 16 21 08254908 16 2125*2549交换0号与3号对象,3号对象就位从0号到3号重新调整为最大堆

第94页：交换（续2）

94211625*082549012345081625*25214902543121 16 0825*254908 162125*2549交换0号与2号对象,2号对象就位从0号到2号重新调整为最大堆

第95页：堆存在于顺序线性表

堆存在于顺序线性表（数组）中160825*212549012345081625*25214902543116 082125*254908162125*2549交换0号与1号对象,1号对象就位从0号到1号重新调整为最大堆

第96页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第97页：7.5 合并排序

977.5合并排序1、合并合并(归并)：把两个或多个有序文件合并成一个单一的有序文件。合并的基本思想：设两个有序表A和B的记录个数(表长)分别为al和bl，变量i和j分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量k是它的当前存放指针。

第98页：都在两个表

9808 21 25 25* 49 62 72 9316 37 54l m m+1ni j08 16 21 25 25* 37 49 54 62 72 93l nkC–当i和j都在两个表的表长内变化时，根据A[i]与B[j]的关键词大小，依次把关键词小的对象排放到新表C[k]中；–当i与j中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表C[k]中。

第99页：算法Merge

合并算法描述：算法Merge(R，t，m，n.X)M1[初始化指针]i←t．j←m＋1．k←1．M2[比较i和j所指记录]WHILE（i≤m）AND（j≤n）DO（IFKi≤KjTHEN（Xk←Ri．i←i＋1.）ELSE（Xk←Rj．j←j＋1.）k←k+1.）M3[复制余留记录]WHILE(i≤m)DO(Xk←Ri.i←i＋1.k←k+1.)WHILE(j≤n)DO(Xk←Rj.j←j＋1.k←k+1.)▌

第100页：算法分析（续2）

Merge算法分析：关键词比较次数≤n-t+1记录移动次数为n-t+1

第101页：算法分析（续）

1012、合并排序：两路合并：一次合并两个文件合并排序：利用两路合并过程进行排序。基本思想：设初始文件有n个记录，首先把它看成是n个长度为1的有序子序列(合并项)，先做两两合并，得到⌈n/2⌉个长度为2的合并项(如果n为奇数，则最后一个有序子序列的长度为1)；再做两两合并…，如此重复，最后得到一个长度为n的有序序列。

第102页：开始

开始255748371292863325,5737,4812,9233,86第一次合并25,37,48,5712,33,86,92第二次合并12,25,33,37,48,57,86,92第三次合并合并排序过程示例

第103页：算法Merge（续2）

算法Merge(R,t,m,n.X)：合并算法，假定文件(Rt,Rt＋1,…,Rm)和(Rm＋1,…,Rn)已经有序，合并这两个文件，得到排序好的新文件(Xt,Xt＋1,…,Xn)；算法MPass(R,n,1ength．X)：一趟合并算法，将文件R中长度为length的所有子文件两两合并到文件X中，n是R记录数，该函数中调用了Merge()；

算法MSort(R，n)：合并排序算法，该函数通过调用函数Mpass()，实现两路合并排序。

第104页：一趟合并MPass

一趟合并MPass(R,n,1ength.X)的基本思想设文件R中的n个记录已经分为一些长度为len的子文件，将这些子文件两两合并，合并成一些长度为2len的子文件，结果放到X中。如果n不是2len的整数倍，则一趟合并到最后，可能遇到两种情形：–剩下一个长度为len的子文件和另一个长度不足len的子文件，可用一次merge算法，将它们合并成一个长度小于2len的子文件。

–只剩下一个子文件，其长度小于或等于len，可将它直接抄到X中。

第105页：算法MPass

一趟归并算法算法MPass(R, n, 1ength．X)MP1 [初始化]i←1．MP2 [合并相邻的两个长度为length的子文件]WHILE i≤n–2*length + 1 DO(Merge(R, i, i＋length-1, i＋2*length-1. X ) .i←i＋2*length．)MP3 [处理余留的长度小于2*length的子文件]IF i+length–1<n THENMerge(R, i, i+length-1, n. X)ELSEFOR j=i TO n DO Xj←Rj．▌

第106页：归并排序算法

归并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16

第107页：算法MSort

两路合并排序算法算法MSort(R, n)//X是辅助文件，其记录结构与R相同MS1 [初始化]length←1．MS2 [交替合并]WHILE length<n DO（MPass(R, n, length. X).length←2*length．MPass(X, n, length. R).length←2*length）▌

第108页：算法分析一趟两路合并

1083、算法分析一趟两路合并MPass，要调用Merge函数⌈n/(2*len)⌉O(n/len)次，而Merge的复杂度为O(len).所以,MPass的复杂度为O(n).合并排序算法MSort，调用MPass正好⌈log2n⌉次，所以算法总的时间复杂度为O(nlog2n)。辅助存储空间：O(n)归并排序是稳定的排序方法。

第109页：通过实例仔细分析合并排序算法

通过实例仔细分析合并排序算法，不难发现它的两个缺点：(1)当数据集非常小时，比如只有2个元素，仍然采用分治策略，影响效率。(2)Merge算法基于元素移动，当元素比较大时会比较费时。针对这两个问题的解决办法：(1)对于非常小的数据集，以及前几次归并动作，调用直接插入排序算法。(2)将数组存储改为链表存储，这样记录移动就变为指针移动了。

第110页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第111页：各种内排序方法

1117.6.1各种内排序方法的比较排序方法最好时间平均时间最坏时间稳定性辅助空间直接选择O(n2)O(n2)O(n2)不稳定O(1)希尔O(n1.25)不稳定O(1)直接插入O(n)O(n2)O(n2)稳定O(1)冒泡O(n)O(n2)O(n2)稳定O(1)快速O(nlog2n)O(nlog2n)O(n2)不稳定O(log2n)堆O(nlog2n)O(nlog2n)O(nlog2n)不稳定O(1)归并O(nlog2n)O(nlog2n)O(nlog2n)稳定O(n)

第112页：1127.6.2 排序下界

1127.6.2排序下界下界：如果一个领域问题的输入规模为n，则“该领域问题的算法的时间复杂性下界为L(n)”含义是：不存在解该领域问题的算法，它的时间复杂性小于L(n).排序下界:O(nlog2n)任何基于关键词比较的排序算法，其关键词比较次数至少为nlog2n。

第113页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第114页：1147.7 分布排序

1147.7分布排序当预先知道待排序关键词的一些知识时，比如其分布范围，就能构造出非基于关键词比较的排序算法，而且有些算法能在最坏情况下达到线性时间。如扑克牌的排序、英文单词的排序等，可采用基于关键词的数字性质的分“桶”排序方法。“桶”个数的选择是根据关键词的数字性质，而且“桶”的个数将直接影响排序算法的效率。

两种分布排序：基数分布和值分布。

第115页：基数分布假定记录

1157.7.1基数分布假定记录R1，R2，…，Rn相应的关键词K1，K2，…，Kn都有如下的表示形式:Ki=(Ki,p，Ki,p–1，…，Ki,1)，且对于每个t(1≤t≤p)都有0≤Ki,t<r，r为基数.基数分布排序是基于关键词的表示，按其字典序由小到大排列。其中，字典序规定如下：Ki=(Ki,p，…，Ki,1)＜Kj=(Kj,p，…，Kj,1)当且仅当存在t≤p，使得当s＞t时Ki,s=Kj,s而Ki,t<Kj,t．

第116页：基数分布排序最高次序位法

基数分布排序最高次序位法：先按高位分桶，然后桶内进行排序如：英文单词，扑克牌最低次序位法：首先按最低位排序，然后按下一个次低位排序，…，最后按最高位排序。

第117页：按最低位分配

1171221630281016*20618按最低位分配r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]1221630281016*206183010201221616*62818r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]1816*1612102203062816*2826121016182030按次低位分配收集收集

第118页：算法RadixSort

算法RadixSort (Q, n, p, r)//最低次序位法的基数排序算法//Q为队列，P是关键词的位数，r为基数RadixSort 1. [形成队列Q]用LINK域链接形成队列QRadixSort 2. [关键词低位到高位分别按基数排序]FORj=1 TOpDO(把队列Q0,Q1, …,Qr–1清空.WHILE NOT( QEmpty(Q) ) DO(X←Q.令X=(K[p],K[p–1], …,K[1]) .QK[j]←X) .合并Q0,Q1, …,Qr–1形成新的Q) ▐

第119页：值分布设记录序列

1197.7.2值分布设记录序列R1，R2，…，Rn，相应的关键词满足u≤Ki≤v且Ki为整数(1≤i≤n)，则使用辅助数组COUNT[u:v]就可得出如下的排序算法。算法D（R,n,u,v.S）D1FORi=uTOvDOCOUNT[i]←0.D2FORj=1TOnDOCOUNT[Kj]←COUNT[Kj]+1.D3FORi=u+1TOvDOCOUNT[i]←COUNT[i]+COUNT[i–1].//此时COUNT[Kj]是关键词等于Kj的所有记录最终排序位置的最大序号D4FORj=nTO1STEP–1DO(i←COUNT[Kj].Si←Rj.COUNT[Kj]←i–1)▐

第120页：果已知

如果已知K1，K2，…，Kn在区间（K0，Kn+1）上的分布是某种熟悉的分布，则可通过这种分布和区间来选择桶。例如，如果K1，K2，…，Kn在（K0，Kn+1）上呈均匀分布，则有b个桶B1，B2，…，Bb，且Bj的定义如下（1≤j≤b）：则给定Ki就可确定一个桶j，然后分别独立地排序各桶，最后把所有的桶合并在一起，形成排序文件。

第121页：按时间代价分类

按时间代价分类，内排序算法大致分为三大类：①简单排序算法，它们一般都比较简单，容易实现，但时间复杂度相对较高，即最坏情况下时间复杂度均为O(n2)，也有一些改进的算法，如Shell排序；②O(nlog2n)类算法，以分治策略算法为主，采用堆结构也可实现，在以比较运算为时间复杂度衡量基准的前提下，此类算法是最优的策略，其平均情况下时间复杂度均为O(nlog2n)；

③线性时间算法，不以关键词比较为基础，有较低的时间代价(即O(n))，但是需要对数据集有一定先验知识，比如数据分布于哪个区间内等等。内排序小结

第122页：讨论的内排序方法中

在讨论的内排序方法中，没有哪一个方法可以称为是最好的，一些方法对较小的n具有较好的性能，而另一些方法对较大的n性能较好。当输入记录是部分有序时，插入排序比较合适，这种方法对于较小的n值，是最好的排序方法。合并排序具有最好的最坏情况性能，但是它比堆排序需要更多的存储空间；快速排序具有最好的平均性能，但它的最坏情况是O(n2)；

基数排序的性能取决于关键词值的范围以及基数r的选择。

第123页：第七章排序目录

第七章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序7.5合并排序7.6基于关键词比较的排序算法分析7.7分布排序7.8外排序

第124页：本章需要复习

本章需要复习的知识点排序的基本概念排序的基本概念关键词、初始关键词排列关键词比较次数、记录移动次数稳定性附加存储空间插入排序用实例表明直接插入排序、折半插入排序和希尔排序的过程直接插入排序和折半插入排序的算法

第125页：排序的性能分析当待排序

排序的性能分析当待排序的关键词序列已经基本有序时，用直接插入排序最快交换排序用实例表明冒泡排序和快速排序的过程冒泡排序和快速排序的算法算法的性能分析快速排序是一个递归的排序法当待排序关键词序列已经基本有序时，快速排序显著变慢。

第126页：选择排序用实例表明直接选择排序

选择排序用实例表明直接选择排序、堆排序的过程直接选择排序和堆排序的算法两种选择排序的性能分析选择排序在一个待排序区间中选出最大的数据时，与区间后一个数据对调，这导致方法不稳定。二路合并排序用实例表明二路合并排序的过程二路合并排序的算法该算法的性能分析合并排序需要较多的附加存储。合并排序对待排序关键词的初始排列不敏感，故排序速度较稳定。

第127页：课后作业

课后作业247页：7-2、7-5、7-18、7-24、7-49；上机实验：7-4、7-11