CHAP10排序lhj

1、1210.1 概述概述10.2 插入类排序插入类排序10.3 交换类排序交换类排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较310.1 概概 述述10.1.1 排序的定义排序的定义10.1.3 排序的分类排序的分类 10.1.4 基本操作基本操作10.1.2 比较的标准比较的标准 10.1.5 内部排序的方法内部排序的方法 410.1.1 排序的概念排序的概念1.排序排序(sorting)是计算机内经常进行的一种操作，是计算机内经常进行的一种操作，其目的是将一组其目的是将一组“无序无序”的记录序列调的记录

2、序列调整为整为“有序有序”的记录序列。的记录序列。例如：例如：成绩表；奖学金评定综合分。成绩表；奖学金评定综合分。52.数据表数据表 (datalist): 它是待排序数据它是待排序数据对象的有限集合。对象的有限集合。3.主关键字主关键字(key): 数据对象有多个属性数据对象有多个属性域域, 即多个数据成员组成即多个数据成员组成, 其中有一个其中有一个属性域可用来区分对象属性域可用来区分对象, 作为排序作为排序依据，称为依据，称为关键字关键字。也称为。也称为排序码排序码。6 一般情况下，一般情况下，假设含假设含n个记录的序列为个记录的序列为 R1, R2, ， Rn 其相应的其相应的关键字序

3、列关键字序列为为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系它们之间存在着这样一个关系 Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作的操作称作排序排序。710.1.2 比较的标准比较的标准稳定性稳定性 不稳定性不稳定性 排序过后能使值相同的数据保排序过后能使值相同的数据保持原顺序中的相对位置持原顺序中的相对位置 排序过后不能使值相同的数据排序过后不能使值相同的数据保持原顺序中的相对位置保持原顺序中的相对位置 4932564927

4、2732494956l 空间复杂度空间复杂度l 时间复杂度时间复杂度l 稳定性稳定性8内部排序内部排序 外部排序外部排序 将欲处理的数据整个存放到内部存将欲处理的数据整个存放到内部存储器中排序，数据可被随机存取储器中排序，数据可被随机存取插入式排序插入式排序 交换式排序交换式排序 选择式排序选择式排序 借助外部的辅助存储器（比如：硬借助外部的辅助存储器（比如：硬盘），由于数据是存在外存中，故盘），由于数据是存在外存中，故数据不可随机被存取数据不可随机被存取 10.1.3 10.1.3 排序的分类排序的分类归并排序归并排序 基数排序基数排序 910.1.4 排序基本操作排序基本操作（1）比较两个

5、排序码的大小；）比较两个排序码的大小；（2）改变指向记录的指针或移动记录）改变指向记录的指针或移动记录本身。本身。 注意：注意： 第第(2)(2)种基本操作的实现依赖于待排序种基本操作的实现依赖于待排序记录的存储方式。记录的存储方式。 所以排序的时间开销可用算法执行中的所以排序的时间开销可用算法执行中的数据比较次数数据比较次数与与数据移动次数数据移动次数来衡量。来衡量。 1010.1.5 内部排序的方法内部排序的方法内部排序的过程是一个逐步扩大内部排序的过程是一个逐步扩大记录的有序序列长度的过程。记录的有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序

6、 列 区1110.1.6 存储方式存储方式1. 地址连续的一组存储单元（地址连续的一组存储单元（记录之间记录之间的次序关系由存储位置决定，实现排序的次序关系由存储位置决定，实现排序必须借助移动记录必须借助移动记录）2. 静态链表（静态链表（记录之间的次序关系由指记录之间的次序关系由指针指示，实现排序不需要移动记录，仅针指示，实现排序不需要移动记录，仅需修改指针需修改指针）链表排序链表排序12存储方式存储方式3. 地址连续的一组存储单元，另设一个地址连续的一组存储单元，另设一个指示各个记录存储位置的地址向量，指示各个记录存储位置的地址向量，在在排序过程中不移动记录本身，而移动地排序过程中不移动记

7、录本身，而移动地址向量中的地址，址向量中的地址，在排序之后再按照地在排序之后再按照地址向量中的值调整记录的存储位置址向量中的值调整记录的存储位置地址排序地址排序13待排记录的数据类型定义如下待排记录的数据类型定义如下:#define MAXSIZE 20 / 待排顺序表最大长度待排顺序表最大长度typedef int KeyType; / 关键字类型为整数类型关键字类型为整数类型typedef struct KeyType key; / 关键字项关键字项 InfoType otherinfo; / 其它数据项其它数据项 RedType; / 记录类型记录类型typedef struct Red

8、Type rMAXSIZE+1; / r0闲置闲置 int length; / 顺序表长度顺序表长度 SqList; / 顺序表类型顺序表类型1410.2 10.2 插插 入入 排排 序序15有序序列有序序列R1.i-1Ri无序序列无序序列 Ri.n一趟直接插入排序的基本思想：一趟直接插入排序的基本思想：有序序列有序序列R1.i无序序列无序序列 Ri+1.n将无序子序列中的将无序子序列中的一个或一个或几个记录几个记录“插入插入”到有序到有序序列中，从而增加记录的序列中，从而增加记录的有序子序列的长度。有序子序列的长度。16实现实现“一趟插入排序一趟插入排序”可分三步进行：可分三步进行：3将将R

9、i 插入插入(复制复制)到到Rj+1的位置上。的位置上。2将将Rj+1.i-1中的所有中的所有记录记录均均后移后移 一个位置；一个位置；1在在R1.i-1中中查找查找Ri的插入位置；的插入位置； R1.j.key Ri.key Rj+1.i-1.key17直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）1810.2.1 直接插入排序直接插入排序利用利用 “顺序查找顺序查找”实现实现 “在在R1.i-1中中

10、查找查找Ri的插入位置的插入位置”。1.算法的实现要点算法的实现要点19例如：例如：49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：排序结果：L.rj+1

11、= L.r0;20（1）从）从Ri-1起向前进行顺序查找，起向前进行顺序查找， 监视哨设置在监视哨设置在R0；R0 = Ri; / 设置设置“哨兵哨兵”循环结束表明循环结束表明Ri的插入位置为的插入位置为 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 从后往前找从后往前找j=i-1插入位置插入位置j+121（2）对于在查找过程中找到的那些关）对于在查找过程中找到的那些关键字不小于键字不小于Ri.key的记录，并在查找的记录，并在查找的同时实现记录向后移动；的同时实现记录向后移动；for (j=i-1; R0.keyRj.key; -j); Rj+1 = R

12、j（3）上述循环结束后可以直接进行）上述循环结束后可以直接进行“插插入入”。L.rj+1 = L.r0;22void InsertionSort ( SqList &L ) / 对顺序表 L 作直接插入排序 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 复制为监视哨复制为监视哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移记录后移L.rj+1 = L.r0; / 插入到正确位置插入到正确位置2.算法实现

13、算法实现233.性能分析性能分析直接插入排序的直接插入排序的基本操作基本操作有两个：有两个：l“移动移动”记录。记录。l“比较比较”序列中两个关键字的大序列中两个关键字的大小；小；24（1）时间复杂度）时间复杂度最好的情况（关键字正序）最好的情况（关键字正序）“比较比较”的次数：的次数：最坏的情况（关键字逆序）最坏的情况（关键字逆序）“比较比较”的次数：的次数：112nni02) 1)(4() 1(2nnini“移动移动”的次数：的次数：“移动移动”的次数：的次数：2) 1)(4() 1(2nnini25平均时间复杂度：平均时间复杂度：O（n2）（2）空间复杂度）空间复杂度 需要一个记录的辅助

14、空间需要一个记录的辅助空间r(0)。（3）稳定性）稳定性 稳定稳定特点：特点：简单、容易实现，简单、容易实现，适用于待适用于待排序记录基本有序或待排序记录较排序记录基本有序或待排序记录较小时。小时。261.基本思想：基本思想：因为因为 R1.i-1 是一个按是一个按关键字有序的有序序列，则可以关键字有序的有序序列，则可以利用利用折半查找实现折半查找实现“在在R1.i-1中中查找查找Ri的的插入位置插入位置”，如此实现的插入排序，如此实现的插入排序为为折半插入折半插入排序。排序。10.2.2 折半插入排序折半插入排序2714 36 49 52 80 58 61 23 97 75ilowhighm

15、mlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如例如:再如再如:插入插入位置位置插入插入位置位置L.rL.rL.rhigh+1 = L.r0; / 插入插入28void BiInsertionSort ( SqList &L ) / BInsertSort/在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 记录后移记录后移L.rhigh+1 = L.r0; / 插入插入2.算法实现算法实现29low = 1;

16、 high = i-1;while (low=high) m = (low+high)/2; / 折半折半if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区插入点在低半区else low = m+1; / 插入点在高半区插入点在高半区/在在 L.r1.i-1中折半查找插入位置中折半查找插入位置（是否完是否完善？善？）303.3.算法分析算法分析(1)(1)稳定性：稳定稳定性：稳定(2)(2)空间复杂度：空间复杂度：O(1)(1)(3)(3)时间复杂度时间复杂度 比较次数与待排记录的初始顺序无关，只依赖比较次数与待排记录的初始顺序无关，只依赖记录个数；记录个

17、数；插入每个记录需要插入每个记录需要O(log(log2 2i)i)次比较次比较最多移动最多移动i+1i+1次，最少次，最少2 2次（临时记录）次（临时记录）最佳情况最佳情况下总时间代价为下总时间代价为O(nlog(nlog2 2n)n) ，最差最差和和平均平均情况下仍为情况下仍为O(n(n2 2) )。319.2.3希尔排序（又称缩小增量排序）希尔排序（又称缩小增量排序）1.基本思想基本思想 把待排序的数据元素分成若干个小组，把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小；当完成了所有序；小组的个数逐次缩小；当

18、完成了所有数据元素都在一个组内的排序后排序过程数据元素都在一个组内的排序后排序过程结束。结束。32例如：例如：6565 343425258787 121238385656 464614147777 92922323565665651414252577778787383823235656343414147777121223236565464625258787929238386565777712123434565612121414656534342323777746462525878792923838121214142323252534343838464656566565777787879292结

19、果序列结果序列d=6d=3d=133void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=L.length ; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; / 记录后移,查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsert2.算法实现算法实现34void ShellSort (SqList &L, int dlta, int t) / 增量为dlta的希尔排序 for (k=0; kt; +k)

20、 ShellInsert(L, dltak); /一趟增量为dltak的插入排序 / ShellSort353.3.算法分析算法分析（1 1）增量序列的选择）增量序列的选择 ShellShell排序的执行时间依赖于增量序列。排序的执行时间依赖于增量序列。 好的增量序列的共同特征：好的增量序列的共同特征： 最后一个增量必须为最后一个增量必须为1 1； 应该尽量避免序列中的值应该尽量避免序列中的值( (尤其是相尤其是相邻的值邻的值) )互为倍数的情况。互为倍数的情况。dlta0=L.length /2+1;for(k=1;kt;k+)dltak=dltak-1/2;363.3.算法分析算法分析（2

21、 2）时间复杂度）时间复杂度 O（n3/2） （3 3）稳定性）稳定性 不稳定。不稳定。3710.3 交换类排序交换类排序通过通过“交换交换”无序序列中的记录从无序序列中的记录从而得到其中而得到其中关键字最小关键字最小或或最大最大的记录，的记录，并将它并将它加入到有序子序列中加入到有序子序列中，以此方法，以此方法增加记录的有序子序列的长度。增加记录的有序子序列的长度。冒泡排序冒泡排序快速排序快速排序3810.3.1 10.3.1 冒泡排序冒泡排序1.1.基本思想基本思想（1 1）依次比较相邻两个数据元素的大小，）依次比较相邻两个数据元素的大小，若逆序则交换两个数据元素，否则不交换。若逆序则交换

22、两个数据元素，否则不交换。（2 2）当完成一趟交换以后，最大的元素）当完成一趟交换以后，最大的元素将会出现在数据序列的最后一个位置。将会出现在数据序列的最后一个位置。（3 3）重复以上过程，直到待排序序列中）重复以上过程，直到待排序序列中没有逆序为止。没有逆序为止。39例如例如 ：493865977613274997979738492713766549384927651349384927134938492713382713767665494938特点：特点：1.n1.n个数排序共需进行个数排序共需进行n-1n-1趟比较趟比较2.2.第第i i趟共需要进行趟共需要进行n-in-i次比较次比较40

23、void bubblf_sort(SqList &L) /自小至大有序 for(i=1,i=L.length-1;+i) for(j=1;jL.length-1;+j) if(LT(L.rj+1.key,L.rj.key) L.rj L.rj+1/bubblf_sort1 15 24 6 17 5 1 15 6 17 5 241 15 6 17 5 241 6 15 5 17 24假设假设L.length=nL.length=n，则总共比较，则总共比较n n2 2次次2.2.冒泡排序算法冒泡排序算法原始算法原始算法41void bubblf_sort(SqList &L) /自

24、小至大有序for(i=1;i=L.length-1;+i) for(j=1;jL.length-i;+j) /n-i已经有序 if(L.rj+1.keyL.rj.key) L.rj L.rj+1/bubblf_sort1 15 24 6 17 5 1 15 6 17 5 241 15 6 17 5 241 6 15 5 17 24注意第注意第i趟比较了趟比较了n-i次，则可以有效的减少比较次数次，则可以有效的减少比较次数比较的总的次数是比较的总的次数是1+2+1+2+n-1=n(n-1)/2+n-1=n(n-1)/2改进算法改进算法42问题：刚才的改进算法是否已经最优问题：刚才的改进算法是否已

25、经最优1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 分析：分析：因为给定的待排序序列已经是一个正序因为给定的待排序序列已经是一个正序的序列，经过第一趟的比较以后，已经的序列，经过第一趟的比较以后，已经没有交没有交换发生换发生，但是算法仍然会继续执行。，但是算法仍然会继续执行。解决：解决：添加一个算法的结束条件添加一个算法的结束条件，即当某一，即当某一趟排序过程中只有比较而没有交换的时候，趟排序过程中只有比较而没有交换的时候，就认定序列已经有序，可以提前结束循环。就认定序列已经有序，可以提前结束循环

26、。改进算法改进算法43void bubblf_sort(SqList &L) 自小至大有序 for(i=1,chang=TRUE;i=L.length-1&chang;+i) chang=FALSE; for(j=1;j=L.length-i;+j) if(L.rj+1.keyL.rj.key) x=L.rj;L.rj+1=L.rj; L.rj =x; chang=TRUE; /end if /end for /bubblf_sort算法实现算法实现443.3.算法分析算法分析（1 1）时间复杂度）时间复杂度最好的情况最好的情况（关键字在记录序列中顺序有序）（关键字在记录序列中

27、顺序有序） 只需进行一趟冒泡只需进行一趟冒泡“比较比较”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）最坏的情况（关键字在记录序列中逆序有序） 需进行需进行n-1趟冒泡趟冒泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-12) 1() 1(2nnini2) 1(3) 1(32nnini45平均时间复杂度平均时间复杂度 O(n2)（2）空间复杂度：）空间复杂度：O(1)（3）稳定性：稳定）稳定性：稳定4610.3.2 10.3.2 快速排序快速排序由于在冒泡排序的扫描过程中只对相邻由于在冒泡排序的扫描过程中只对相邻的元素进行比较，因此，在交换

28、两个元素的元素进行比较，因此，在交换两个元素时，只能消除一个逆序。时，只能消除一个逆序。 如果能通过如果能通过两个不相邻元素的交换两个不相邻元素的交换，消，消除多个逆序，则会大大加快排序的速度。除多个逆序，则会大大加快排序的速度。 快速排序可以实现之。快速排序可以实现之。471.算法思想算法思想（1）找一个记录，以它的关键字作为找一个记录，以它的关键字作为“枢轴枢轴”，凡其，凡其关键字小于枢轴关键字小于枢轴的记录均的记录均移动至该记录之前，移动至该记录之前，反之，凡反之，凡关键字大于关键字大于枢轴枢轴的记录均的记录均移动至该记录之后移动至该记录之后。Ls.i-1 枢轴枢轴 Li+1.t（2）对

29、分割）对分割 后的两个子表重复上述过程，后的两个子表重复上述过程，直到子表的表长不超过直到子表的表长不超过1为止。为止。48例如例如 ：49 38 65 97 76 13 27 49pivotkey=49lowhigh27low65high13low97highhigh49第一趟结果：第一趟结果： 27 38 13 27 38 13 4949 76 97 65 76 97 65 4949 小于小于49大于等于大于等于494949 在调整过程中，对枢轴记录的赋值是多在调整过程中，对枢轴记录的赋值是多余的，一趟排序结束后，余的，一趟排序结束后，low=high的位置的位置才是枢轴记录的最后位置。才

30、是枢轴记录的最后位置。 因此，因此，R0=Rlow，一趟结束后，一趟结束后， Rlow = R0 /枢轴直接定位 不需要不需要进行记录的多次进行记录的多次“交换交换”。50int Partition (SqList &L, int low, int high) / Partition L.r 0 = L.r low; pivotkey = L.r low.key; while (lowhigh) while(low=pivotkey) - high; / 从右向左搜索L.r low = L.r high;while (lowhigh & L.r low.key=pivotkey

31、) + low; / 从左向右搜索L.r high = L.r low;L.r low = L.r0; return low;2.算法实现算法实现51void QSort (SqList &L,int low, int high ) / 对记录序列Llow.high进行快速排序 if (low high) / 长度大于1 / QSortpivotloc = Partition(L, low, high); / 对 Llow.high 进行一次划分一次划分QSort(L, low, pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置是枢轴位置QSort(L, pi

32、votloc+1, high); / 对高子表递归排序52void QuickSort( SqList & L) / 对顺序表进行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次调用函数第一次调用函数 Qsort 时，待排序记录时，待排序记录序列的上、下界分别为序列的上、下界分别为 1 和和 L.length。533. 算法分析算法分析（1）时间复杂度）时间复杂度假设假设一次划分所得枢轴位置一次划分所得枢轴位置 i=k，则对，则对n 个个记录进行快排所需时间：记录进行快排所需时间：其中其中 Tpass(n)为对为对 n 个记录进行一次划分个记录

33、进行一次划分所需时间。所需时间。T(n) = Tpass(n) + T(k-1) + T(n-k)54最坏情况最坏情况 O(n2)最好情况最好情况 O(n log2n )平均平均 O(nlogn)（2 2）空间复杂度）空间复杂度若每次划分较为均匀，则其递归树的高若每次划分较为均匀，则其递归树的高度为度为O(lgn)O(lgn)，故递归后需栈空间为，故递归后需栈空间为O(lgn)O(lgn)。最坏情况下，递归树的高度为。最坏情况下，递归树的高度为O(n)O(n)，所需的栈空间为，所需的栈空间为O(n)O(n)。（3 3）稳定性）稳定性 不稳定不稳定 。5510.4 选择类排序选择类排序10.4.

34、1 10.4.1 简单选择排序简单选择排序10.4.2 10.4.2 树形选择排序树形选择排序10.4.3 10.4.3 堆排序堆排序56选择类排序的算法思想：选择类排序的算法思想：假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列R1.i-1无序序列无序序列 Ri.n 第第 i 趟排序趟排序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列R1.i无序序列无序序列 Ri+1.n5710.4.1 简单选择排序简单选择排序1.算法思想算法思想有序序列有序序列R1.i-1无序序列无序序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选

35、出从中选出关键字最小的记录关键字最小的记录有序序列有序序列R1.i无序序列无序序列 Ri+1.n58例如：例如：149238365497576613727849ki=1jkjjjjkjjk134959例如：例如：149238365497576613727849kjjjjjj1349k k2602.算法实现算法实现void SelectSort (SqList &L) / 对记录序列R1. L.length作简单选择排序 for (i=1; iL.length; +i) k=i; / SelectSortfor (j=i+1; j=L.length ; +j) if(L.rj.keyL.

36、rk.key)k=j;if (i!=k) Swap(L.ri ,L.rk ); /交换613.算法分析算法分析（1）时间复杂度）时间复杂度 最坏情况：最坏情况：3(3(n n-1)-1)次次移动次数：移动次数：最好情况（正序）：最好情况（正序）：0 0次次比较次数：比较次数：)() 1(21211nOnninni ）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为O O( (n n2 2) )。62（2）空间复杂度）空间复杂度 O(1)（3）稳定性）稳定性 不稳定不稳定 。6310.4.2 树形选择排序树形选择排序( (锦标赛排序锦标赛排序) )1.基本思想基本思想（1 1）取得）取得

37、n n 个对象的关键码，进行个对象的关键码，进行两两两比较两比较，得到，得到 n/2 n/2 个比较的优胜者个比较的优胜者( (关关键码小者键码小者) )，作为第一步比较的结果保留，作为第一步比较的结果保留下来。下来。（2 2）这）这 n/2 n/2 个对象再进行关键码的个对象再进行关键码的两两两比较两比较，如此重复，直到选出一个，如此重复，直到选出一个关键码最小的对象为止。关键码最小的对象为止。64133813973865493876131327652749例如：例如：65139749387613652749381338651327273827386576276627974938761365

38、27493827386576271338384938657649672.算法分析算法分析（1）含有）含有n个叶子节点的完全二叉树的个叶子节点的完全二叉树的深度为深度为log2n+1，则选择排序的每一趟都则选择排序的每一趟都需作需作log2n次比较，排序的时间复杂度次比较，排序的时间复杂度O(nlog2n)。（2）需要辅助存储空间较多（）需要辅助存储空间较多（n-1），），和最大值作多余的比较等等。和最大值作多余的比较等等。6810.4.3 堆排序堆排序1.堆：堆：把待排序的数据元素存放在数组中把待排序的数据元素存放在数组中r1r1nn，把，把r r看成是一棵完全二叉树，每看成是一棵完全二叉树，

39、每个结点表示一个记录。个结点表示一个记录。riri结点的左孩子结点的左孩子是是r2ir2i，右孩子是，右孩子是r2i+1r2i+1。 若若ri.key=r2i.keyri.key=r2i.key，并且，并且 ri.key=r2i+1.keyri.key=r2i.keyri.key=r2i.key，并且，并且 ri.key=r2i+1.keyri.key=r2i+1.key，则称此完全二，则称此完全二叉树为堆。（大根堆）叉树为堆。（大根堆）大根堆大根堆小根堆小根堆712.堆排序算法思想（以小根堆为例）堆排序算法思想（以小根堆为例）（1 1）以初始关键字序列，）以初始关键字序列，建立堆建立堆； （

40、2 2）输出堆顶最小元素；）输出堆顶最小元素；（3 3）调整调整余下的元素，使其成为一个新余下的元素，使其成为一个新堆；堆；（4 4）重复）重复2,32,3步，直到步，直到n n个元素输出，得个元素输出，得到到 一个有序序列。一个有序序列。关键问题：关键问题：（1 1）如何由一个无序序列建成一个堆）如何由一个无序序列建成一个堆? ? （2 2）如何调整余下的元素成为一个新堆）如何调整余下的元素成为一个新堆? ? 72例如，堆调整过程例如，堆调整过程1338277697654949rc=1373void HeapAdjust (HeapType &H, int s, int m) / 已

41、知 H.r s.m中记录的关键字除 H.r s 之外均 / 满足堆的特征，本函数自上而下调整 H.r s 的 / 关键字，使 H.r s.m 也成为一个大顶堆。 / HeapAdjustrc = H.r s; / 暂存 H.r s for ( j=2*s; j= H.rj.key ) break; / 再作“根”和“子树根”之间的比较， / 若“=”成立，则说明已找到 rc 的插 / 入位置 s ，不需要继续往下调整H.rs = H.rj; s = j; / 否则记录上移，尚需继续往下调整if ( jm & H.rj.key0; -i ) HeapAdjust ( H, i, H.le

42、ngth ); / 建大顶堆for ( i=H.length; i1; -i ) H.r1H.ri; / 将堆顶记录和当前未经排序子序列 / H.r1.i中最后一个记录相互交换 HeapAdjust(H, 1, i-1);/将H.r1.i-1重新调整为大顶堆773.3.算法分析算法分析（1） 时间复杂度时间复杂度 O(nlog2n)（2） 空间复杂度空间复杂度 O(1)（3） 稳定性稳定性 不稳定不稳定7810.5 归归 并并 排排 序序1.基本思想基本思想 将一个具有将一个具有n n个待排序记录的序列个待排序记录的序列看成是看成是n n个长度为个长度为1 1的有序序列，然后进的有序序列，然后

43、进行行两两归并两两归并，得到得到n n/2/2个长度为个长度为2 2的有序的有序序列，序列，再进行两两归并，得到再进行两两归并，得到n n/4/4个长个长度为度为4 4的有序序列，的有序序列，直至得到一，直至得到一个长度为个长度为n n的有序序列为止。的有序序列为止。79例如：归并排序过程例如：归并排序过程 (49) (38) (65) (97) (76) (13) (27)(38 49) (38 49 65 97)(65 97)(13 76)(27)(13 27 38 49 65 76 97) (13 27 76)80void Merge (RedType SR, RedType TR, i

44、nt i, int m, int n) / 将有序的记录序列 SRi.m 和 SRm+1.n / 归并为有序的记录序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 将SR中记录由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; 2.2.算法实现算法实现81if (i=m) / 将剩余的 SRi.m 复制到 TR while(i=m)TRk+.key = SRi+.key; if (j=n) / 将剩余的 SRj.n 复制到 TR while(j=n)TRk+.key =

45、 SRj+.key; 82void Msort ( RedType SR, RedType &TR1, int s, int t ) / 将SRs.t 归并排序为 TR1s.t if (s= =t) TR1s=SRs; else / Msort 83m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.mMsort (SR, TR2, m+1, t); /递归地SRm+1.t归并为有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 将TR2s.m和T

46、R2m+1.t归并到TR1s.t84void MergeSort (SqList &L) / 对顺序表 L 作2-路归并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，对容易看出，对 n 个记录进行归并排序的个记录进行归并排序的时间复杂度为时间复杂度为(nlogn)。即：即： 每一趟归并的时间复杂度为每一趟归并的时间复杂度为 O(n)， 总共需进行总共需进行 log2n 趟。趟。853.算法分析算法分析（1）时间复杂度）时间复杂度每一趟归并的时间复杂度为每一趟归并的时间复杂度为 O(n)， 总共总共需进行需进行 log2n 趟。所以对趟

47、。所以对 n 个记录进行个记录进行归并排序的时间复杂度为归并排序的时间复杂度为(nlog2n)。（2）空间复杂度）空间复杂度 O（n）（3）稳定性：）稳定性：稳定稳定86基数排序是一种借助基数排序是一种借助“多关键字多关键字排序排序”的思想来实现的思想来实现“单关键字排单关键字排序序”的内部排序算法。的内部排序算法。10.6.1 多关键字的排序多关键字的排序10.6.2 链式基数排序链式基数排序10.6 基基 数数 排排 序序8710.6.1 多关键字的排序多关键字的排序1.多关键字多关键字n 个记录的序列个记录的序列 R1, R2, ，Rn对关键字对关键字 (Ki0, Ki1, ,Kid-1

48、) ) 有序有序是指：是指： 其中其中: : K0 被称为被称为 “最主最主”位关键字，位关键字，Kd-1 被称为被称为 “最次最次”位关键字位关键字。 对于序列中任意两个记录对于序列中任意两个记录 Ri 和和 Rj(1ijn) 都都满足满足下列下列(词典词典)有序有序关系：关系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) )88 实现多关键字排序实现多关键字排序通常有两种方法通常有两种方法: :最低位优先最低位优先LSD法法最高位优先最高位优先MSD法法89先对先对K0进行排序进行排序，并按，并按 K0 的不同的不同值将记录序列值将记录序列分成若

49、干子序列分成若干子序列之之后，后，分别对分别对 K1 进行排序进行排序，.， 依次类推，依次类推，直至最后对最次位关直至最后对最次位关键字排序完成为止键字排序完成为止。(组内再排组内再排)2.2.最高位优先最高位优先MSD法法90例如例如: :学生记录含三个关键字学生记录含三个关键字: :系别系别、班号班号和和班内的班内的序列号，其中以序列号，其中以系别为最主位关键字。系别为最主位关键字。 无序序列无序序列对对K0排序排序对对K1排序排序对对K2排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,182,1,203,2,303,1,201,2,152,1,2

50、02,3,183,1,203,2,30 1,2,152,1,202,3,183,1,203,2,30MSD的排序过程如下的排序过程如下: :91 先对先对 Kd-1 进行排序进行排序，然后对然后对 Kd-2 进行排序，依次类推，进行排序，依次类推，直至对最主位关直至对最主位关键字键字 K0 排序完成为止排序完成为止。3.3.最低位优先最低位优先LSD法法92例如例如: :学生记录含三个关键字学生记录含三个关键字: :系别系别、班号班号和和班内的班内的序列号，其中以序列号，其中以系别为最主位关键字。系别为最主位关键字。 无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,30

51、1,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下的排序过程如下: :9310.6.2 链式基数排序链式基数排序1.1.算法思想算法思想 基数排序是按组成关键字的各位的值基数排序是按组成关键字的各位的值进行进行分配分配和和收集收集，与前面介绍的排序方法，与前面介绍的排序方法不同，它无需进行关键字之间的比较。不同，它无需进行关键字之间的比较。 设关键字有设关键字有d d 位，每位的取值范围为位，每位

52、的取值范围为 r(r(称为基数称为基数) )，则需要进行，则需要进行d d 趟分配与收趟分配与收集，需要设立集，需要设立r r个队列。个队列。例如例如，关键字是，关键字是4 4位字符串，需要位字符串，需要2626个队个队列，列，4 4趟分配与收集；关键字趟分配与收集；关键字3 3位十进制数，位十进制数，需要需要1010个队列，个队列，3 3趟分配与收集。趟分配与收集。94例如：例如：对下列这组关键字对下列这组关键字 278,109,063,930,589,184,505,269,008,083 (1)首先按其首先按其 “个位数个位数” 取值分别为取值分别为 0, 1, , 9 “分配分配” 成

53、成 10 组，之后按从组，之后按从 0 至至 9 的顺序将的顺序将 它们它们 “收集收集” 在一起在一起;(2)然后按其然后按其 “十位数十位数” 取值分别为取值分别为 0, 1, , 9 “分配分配” 成成 10 组，之后再按从组，之后再按从 0 至至 9 的顺序将的顺序将它们它们 “收集收集” 在一起；在一起；(3)(3)最后按其最后按其“百位数百位数”重复一遍上述操作。重复一遍上述操作。95在计算机上实现基数排序时，为减少在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结所需辅助存储空间，应采用链表作存储结构构，即链式基数排序，具体作法为：即链式基数排序，具体作法为：

54、待排序记录以指针相链，构成一个链表；待排序记录以指针相链，构成一个链表；“分配分配” 时，按当前时，按当前“关键字位关键字位”所取值，所取值，将记录分配到不同的将记录分配到不同的 “链队列链队列” 中，每个队中，每个队列中记录的列中记录的 “关键字位关键字位” 相同；相同；“收集收集”时，按当前关键字位取值从小到时，按当前关键字位取值从小到大将大将各队列首尾相链成一个链表各队列首尾相链成一个链表; ;对每个关键字位均重复对每个关键字位均重复 2) 和和 3) 两步。两步。96278109063930589184505269808083 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9

55、 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 278pp109p063p930p589p184p505p269p808p083930063083184505278808109589269 基数排序过程基数排序过程97基数排序过程基数排序过程930063083184505278808109589269 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 083pp505p930pp808p278p109p184p505808109930063269278083184589 063p26958998基数排序过程基数排序过程505808109930063269278083184589f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 109pp063p505pp278p269p083p930p06308310