数据结构第章 排序幻灯片.ppt

《数据结构第章 排序幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第章 排序幻灯片.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构 第 章 排序第1页，共45页，编辑于2022年，星期六教学内容教学内容1、插入排序（直接插入排序、折半插入排序、插入排序（直接插入排序、折半插入排序、希尔排序）；希尔排序）；2、交换排序（起泡排序、快速排序）；、交换排序（起泡排序、快速排序）；3、选择排序（直接选择排序、堆排序）；、选择排序（直接选择排序、堆排序）；4、归并排序；、归并排序；5、基数排序；、基数排序；第2页，共45页，编辑于2022年，星期六 排序：排序：将数据元素的一个任意序列，重新排列成一个将数据元素的一个任意序列，重新排列成一个按关键按关键按关键按关键 字有序字有序字有序字有序的序列。的序列。10.1 概述概述

2、 例：将关键字序列：例：将关键字序列：52,49,80,36,14,58,61,23 调整为：调整为：14,23,36,49,52,58,61,80 一般情况下，假设含一般情况下，假设含 n 个记录的序列为个记录的序列为 R1,R2,Rn，其相应的关键字序列为其相应的关键字序列为 K1,K2,Kn R R1 1,R R2 2,R R3 3,R R4 4,R R5 5,R R6 6,R R7 7,R R8 8 K K1 1,K K2 2,K K3 3,K K4 4,K K5 5,K K6 6,K K7 7,K K8 8 这些关键字相互之间可以进行比较，即在它们之间存在着这这些关键字相互之间可以进

3、行比较，即在它们之间存在着这 样一个关系样一个关系：Kp1Kp2KpnKp1 Kp2 Kp3 Kp4 Kp5 Kp6 Kp7 Kp8 按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1,Rp2,Rpn 的操作称作的操作称作排序排序排序排序。Rp1,Rp2,Rp3,Rp4,Rp5,Rp6,Rp7,Rp8 第3页，共45页，编辑于2022年，星期六 若若 Ki 为记录为记录 Ri 的的主主主主关键字，则排序关键字，则排序结果惟一结果惟一结果惟一结果惟一。若若 Ki 为记录为记录 Ri 的的次次次次关键字，则排序关键字，则排序结果结果结果结果可以可以不惟一不惟一不惟一不

4、惟一（因为（因为 会有相同的关键字）。会有相同的关键字）。设设 Ki=Kj(1in,1jn,ij)，且在排序前的序列中，且在排序前的序列中 Ri 领先于领先于 Rj（即（即 i j）。若在排序后的序列中）。若在排序后的序列中 Ri 仍领先于仍领先于 Rj，则，则 称所用的称所用的排序方法是稳定的排序方法是稳定的排序方法是稳定的排序方法是稳定的；反之，则称所用的；反之，则称所用的排序方法是不稳排序方法是不稳排序方法是不稳排序方法是不稳 定的定的定的定的。例：例：设排序前的关键字序列为：设排序前的关键字序列为：52,49,80,36,14,58,3636,23 若排序后的关键字序列为：若排序后的关

5、键字序列为：14,23,36,3636,49,52,58,80，则则排序方法是稳定的排序方法是稳定的排序方法是稳定的排序方法是稳定的。若排序后的关键字序列为：若排序后的关键字序列为：14,23,3636,36,49,52,58,80，则则排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的。第4页，共45页，编辑于2022年，星期六排序方法分类：排序方法分类：内部排序：内部排序：待排序记录放在内存，待排序记录放在内存，排序过程不需访问外存；排序过程不需访问外存；外部排序：外部排序：排序过程需要访问外存。排序过程需要访问外存。1)、插入排序：、插入排序：直接插入排序、折半插入

6、排序、希尔排序直接插入排序、折半插入排序、希尔排序 2)、交换排序：、交换排序：冒泡排序、快速排序冒泡排序、快速排序 3)、选择排序：、选择排序：简单选择排序、堆排序简单选择排序、堆排序 4)、归并排序：、归并排序：2-路归并排序路归并排序 5)、基数排序、基数排序 按待排序记录所在位置按待排序记录所在位置 按排序依据原则按排序依据原则 按排序所需工作量按排序所需工作量 简单的排序方法：简单的排序方法：T(n)=O(n)先进的排序方法：先进的排序方法：T(n)=O(nlogn)基数排序：基数排序：T(n)=O(d(n+rd)第5页，共45页，编辑于2022年，星期六10.2 插入排序插入排序

7、10.2.1 直接插入排序直接插入排序 初始状态初始状态4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i=2 i=3 3849659776132749 i=4 3849659776132749 i=5 384965769713274976i=6 384965769713274913i=7 384965769713274927i=8 3849657697132749494938659776132749 383849387 趟趟 排序排序 1 趟趟 排序排序 2 趟趟 排序排序 void InsertSort(SqList&L)/对顺序表对顺序表 L 作直

8、接插入排序。作直接插入排序。for(i=2;i=L.length;+i)if(L.ri.key L.ri-1.key)/InsertSort L.r0=L.ri;/复制为监视哨复制为监视哨 L.ri=L.ri-1;for(j=i-2;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移记录后移 L.rj+1=L.r0;/插入到正确位置插入到正确位置 排序过程：排序过程：先将序列中第先将序列中第 1 个记录看成是一个有序子序列，个记录看成是一个有序子序列，然后从第然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。个记录开始，逐个进行插入，直至整个序列有序。第6页，

9、共45页，编辑于2022年，星期六比较次数和移动次数均比较次数和移动次数均约约约约为：为：T(n)=O(n)算法评价算法评价 时间复杂度：时间复杂度：比较次数：比较次数：移动次数：移动次数：0 最好的情况：最好的情况：待排序记录按关键字从小到大排列（正序）待排序记录按关键字从小到大排列（正序）比较次数：比较次数：移动次数：移动次数：最坏的情况：最坏的情况：待排序记录按关键字从大到小排列（逆序）待排序记录按关键字从大到小排列（逆序）一般情况：一般情况：待排序记录是随机的，取平均值。待排序记录是随机的，取平均值。空间复杂度：空间复杂度：S(n)=O(1)直接插入排序是稳定排序直接插入排序是稳定排序

10、 5 4 3 2 1 1 1第7页，共45页，编辑于2022年，星期六10.2.2 其他插入排序其他插入排序 1、折半插入排序：、折半插入排序：用折半查找方法确定插入位置的排序。用折半查找方法确定插入位置的排序。void BInsertSort(SqList&L)for for(i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;while(low=high)m=(low+high)/2;/折半折半 if(L.r0.key =high+1;-j)L.rj+1=L.rj;/记录后移记录后移 L.rhigh+1=L.r0;/插入插入 /forfor/BInsert

11、Sorti=1 (30)13 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85)20 i=8 20 (6 13 30 39 42 70 85)20 lhmmi=8 20 (6 13 30 39 42 70 85)20 lhi=8 20 (6 13 30 39 42 70 85)20 lhi=8 20 (6 13 20 30 39 42 70 85)i=8 20 (6 13 30 39 42 70 85)20 lhmT(n)=O(n)时间复杂度：时间复杂度：空间复杂度：空间复杂度：S(n)=O(1)折半插入排序是稳定排序折半插入排序是稳定排序 仅减少了比较次

12、数，仅减少了比较次数，移动次数不变。移动次数不变。第8页，共45页，编辑于2022年，星期六第二趟希尔排序第二趟希尔排序 第三趟分组，设第三趟分组，设 d3=1 10.2.3 希尔排序（缩小增量排序）希尔排序（缩小增量排序）基本思想：基本思想：对待排序列先作对待排序列先作“宏观宏观”调整，再作调整，再作“微观微观”调整。调整。排序过程：排序过程：先取一个正整数先取一个正整数 d1 n，把所有相隔把所有相隔 d1 的记录放的记录放 在一组内，组内进行直接插入排序；然后取在一组内，组内进行直接插入排序；然后取 d2 d1，重复上述分重复上述分 组和排序操作；直至组和排序操作；直至 di=1，即所有

13、记录放进一个组中排序为止。即所有记录放进一个组中排序为止。其中其中 d di i 称为称为增量增量增量增量。例：例：49 38 65 97 76 13 27 49 55 04 第一趟希尔排序第一趟希尔排序 13 27 49 55 04 49 38 65 97 76 13 04 49 38 27 49 55 65 97 76第三趟希尔排序第三趟希尔排序 第一趟分组，设第一趟分组，设 d1=5 49 38 65 97 76 13 27 49 55 04 13 27 49 55 04 49 38 65 97 76 第二趟分组，设第二趟分组，设 d2=3 04 13 27 38 49 49 55 65

14、 76 97第9页，共45页，编辑于2022年，星期六希尔排序特点：希尔排序特点：分组不是简单的分组不是简单的“逐段分割逐段分割”，而是将相隔某个增量的记录组成，而是将相隔某个增量的记录组成 一个子序列。一个子序列。增量序列取法增量序列取法 希尔最早提出的选法是希尔最早提出的选法是 di=n/2，di+1=di/2。克努特克努特(Knuth)提出的选法是提出的选法是 di+1=di/3。还有其他不同的取法。还有其他不同的取法。如何选择增量序列以产生最好的排序效果，至今仍没有从数学如何选择增量序列以产生最好的排序效果，至今仍没有从数学 上得到解决。上得到解决。1)、没有除、没有除 1 以外的公因

15、子；以外的公因子；2)、最后一个增量值必须为、最后一个增量值必须为 1。希尔排序可提高排序速度希尔排序可提高排序速度 1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。记录跳跃式前移，在进行最后一趟排序时，已基本有序。2)、分组后、分组后 n 值减小，值减小，n2 更小，而更小，而 T(n)=O(n2)，所以所以 T(n)从从 总体上看是减小了。总体上看是减小了。2 2第10页，共45页，编辑于2022年，星期六10.3 交换排序交换排序 1、冒泡排序、冒泡排序 v 排序过程排序过程 1、比较第一个记录与第二个、比较第一个记录与第二个 记录，若记录，若关键字关键字为逆序为逆序则交换；然则

16、交换；然 后比较第二个记录与第三个记录；后比较第二个记录与第三个记录；依次类推，直至第依次类推，直至第 n-1 个记录和第个记录和第 n 个记录比较为止个记录比较为止第一趟冒泡第一趟冒泡第一趟冒泡第一趟冒泡 排序排序排序排序，结果关键字最大的记录被安，结果关键字最大的记录被安 置在最后一个记录上。置在最后一个记录上。2、对前对前 n-1 个记录进行第二个记录进行第二 趟冒泡排序，结果使关键字次大的趟冒泡排序，结果使关键字次大的 记录被安置在第记录被安置在第 n-1 个记录位置。个记录位置。3、重复上述过程，直到重复上述过程，直到 “在在 一趟排序过程中没有进行过交换记一趟排序过程中没有进行过交

17、换记 录的操作录的操作”为止。为止。初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 9797 38 49 65 76 13 27 49 979738 49 65 13 27 49 76 76 第第 二二 趟趟 排排 序序 38 49 13 27 49 65 65 第第 三三 趟趟 排排 序序 38 13 27 49 4949 第第 四四 趟趟 排排 序序 13 27 3849 49 第第 五五 趟趟 排排 序序 13 13 27 27 38 38 第第

18、 六六 趟趟 排排 序序 for(j=1;j n n ;j+)if (r j+1 r j)r j r j+1 ;for(j=1;j n n-1-1;j+)if (r j+1 1;i-)i i ;while(i 1)/while i=n;i=k;Void BubbleSort(SqList&L)冒泡排序算法冒泡排序算法冒泡排序算法冒泡排序算法 初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 k=j;/交换的位置交换的位置 k=1;第11页，共45页，编辑于2022年，星期六v 算法评价算法评价 时间复杂度：时间复杂度：最好情况（正序）最好情况（正序）比较次数：比较次

19、数：n-1 移动次数：移动次数：0 T(n)=O(n)最坏情况（逆序）最坏情况（逆序）比较次数：比较次数：移动次数：移动次数：T T(n n)=)=O O(n n2 2)空间复杂度：空间复杂度：S(n)=O(1)稳定性：稳定排序稳定性：稳定排序 第12页，共45页，编辑于2022年，星期六一般取第一个记录一般取第一个记录 基本思想：基本思想：任选任选任选任选一个记录，以它的关键字作为一个记录，以它的关键字作为“枢轴枢轴枢轴枢轴”，凡关，凡关 键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录 均移至枢轴之后。均移至枢轴之后。2、一趟

20、快速排序（一次划分）、一趟快速排序（一次划分）lowhigh设设 Rs=52 为枢轴。为枢轴。例：例：52 52 52 49 80 36 14 58 61 97 23 75 st 附设两个指针附设两个指针 low 和和 high，从，从 high 所指位置起向前搜索找所指位置起向前搜索找 到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后 从从 low 所指位置起向后搜索找到第一个关键字大于枢轴的关键字所指位置起向后搜索找到第一个关键字大于枢轴的关键字 的记录与枢轴记录交换，重复这两步直至的记录与枢轴记录交换，重复这两步直至 low

21、=high 为止。为止。high23 lowlow80highhighhighhigh14lowlow5252第13页，共45页，编辑于2022年，星期六int Partition(SqList&L,int low,int high)pivotkey=L.rlow.key;/用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 while(low high)while(low=pivotkey)-high;L.rlowL.rhigh;L.rlowL.rhigh;/将比枢轴小的记录交换到低端将比枢轴小的记录交换到低端 while(low high&L.rlow.key=pivotkey)+l

22、ow;L.rlowL.rhigh;L.rlowL.rhigh;/将比枢轴大的记录交换到高端将比枢轴大的记录交换到高端 /while return low;/返回枢轴所在位置返回枢轴所在位置/PartitionL.r0=L.rlow;L.rlow=L.rhigh;L.rhighL.rhigh=L.r0;L.r0=L.rlow;L.rlowL.rlow=L.rhigh;L.rhigh=L.r0;L.r0=L.rlow;L.rlow=L.r0;L.rlow=L.rhigh;L.rlow=L.rhigh;/将比枢轴小的记录移到低端将比枢轴小的记录移到低端 L.rhigh=L.rlow;L.rhigh=

23、L.rlow;/将比枢轴大的记录移到高端将比枢轴大的记录移到高端 3 3第14页，共45页，编辑于2022年，星期六快速排序过程快速排序过程 3、快速排序、快速排序 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，之后分别对分割，之后分别对分割 所得两个子序列所得两个子序列“递归递归”进行一趟快速排序。进行一趟快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴 一次划分一次划分 分别进行一趟快速排序分别进行一趟快速排序 有有 序序 的的 记记 录录 序序 列列 第15页，共45页，编辑于2022年，星期六

24、void QSort(SqList&L,int low,int high)/对顺序表对顺序表 L 中的子序列中的子序列 L.rlow.high 进行快速排序进行快速排序 if(low high)/长度大于长度大于1 /QSortpivotloc=Partition(L,low,high);pivotloc=Partition(L,low,high);/对对对对 L.rlow.high L.rlow.high 进行一次划分进行一次划分进行一次划分进行一次划分 QSort(L,low,pivotloc-1);/对低子序列递归排序，对低子序列递归排序，pivotloc 是枢轴位置是枢轴位置 QSor

25、t(L,pivotloc+1,high);/对高子序列递归排序对高子序列递归排序 第一次调用函数第一次调用函数 Qsort 时，待排序记录序列的上、时，待排序记录序列的上、下界分别为下界分别为 1 和和 L.length。void QuickSort(SqList&L)/对顺序表进行快速排序对顺序表进行快速排序 QSort(L,1,L.length);/QuickSort 第16页，共45页，编辑于2022年，星期六 快速排序实质上是对冒泡排序的一种改进，它的效率与冒泡排序相比有快速排序实质上是对冒泡排序的一种改进，它的效率与冒泡排序相比有很大地提高。在冒泡排序过程中是对相邻两个记录进行关键字

26、比较和互换的，很大地提高。在冒泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样每次交换记录后，只能改变一对逆序记录，而快速排序则从待排序记录这样每次交换记录后，只能改变一对逆序记录，而快速排序则从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能改变几对逆序记录，从而加快了排序速度。改变几对逆序记录，从而加快了排序速度。到目前为止快速排序是平均速度到目前为止快速排序是平均速度最大的一种排序方法最大的一种排序方法，但当原始记录排列基本有序或基本逆序时，每一趟的，但当原始记录排列基本有序或基本逆序时

27、，每一趟的基准记录有可能只将其余记录分成一部分，这样就降低了时间效率，所以快基准记录有可能只将其余记录分成一部分，这样就降低了时间效率，所以快速排序适用于原始记录排列杂乱无章的情况。速排序适用于原始记录排列杂乱无章的情况。快速排序是一种不稳定的排序，在递归调用时需要占据一定的存储空间快速排序是一种不稳定的排序，在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。用来保存每一层递归调用时的必要信息。第17页，共45页，编辑于2022年，星期六10.4 选择排序选择排序 10.4.1 简单选择排序简单选择排序 排序过程：排序过程：首先通过首先通过 n 1 次关键字比较，从次关键字

28、比较，从 n 个记录中找出个记录中找出关键字最小关键字最小的的 记录，将它与第一个记录交换。记录，将它与第一个记录交换。再通过再通过 n 2 次比较，从剩余的次比较，从剩余的 n 1 个记录中找出关键字次小的个记录中找出关键字次小的 记录，将它与第二个记录交换。记录，将它与第二个记录交换。重复上述操作，共进行重复上述操作，共进行 n 1 趟排序后，排序结束。趟排序后，排序结束。第18页，共45页，编辑于2022年，星期六j+if(L.rj.key L.rk.key)k=j;j=i+1;for(i=1;i L.length;+i)例：例：初始：初始：49 38 65 97 76 13 27 jj

29、jjjjki=1 13 49 一趟：一趟：13 38 65 97 76 49 27 i=2 二趟：二趟：13 27 65 97 76 49 38 三趟：三趟：13 27 38 97 76 49 65 四趟：四趟：13 27 38 49 76 97 65 五趟：五趟：13 27 38 49 65 97 76 六趟：六趟：13 27 38 49 65 76 97 排序结束：六趟：排序结束：六趟：13 27 38 49 65 76 97 kk=i;kfor(j=i+1;j=n;j+)if(L.rj.key L.rk.key)k=j;if(i!=k)L.riL.r j;/与第与第 i 个记录交换个记录

30、交换i=6 void SelectSort(SqList&L)/对顺序表对顺序表 L 作简单选择排序。作简单选择排序。/SelectSort i=3 i=4 i=5 比较次数比较次数 n-1 n-2 n-6 比较次数：比较次数：移动次数：移动次数：正序：最小值为正序：最小值为 0；最大值为最大值为 3(n-1)。前前 n 1 个为正序，第个为正序，第 n 个记录的关键字最小。个记录的关键字最小。时间复杂度：时间复杂度：时间复杂度：时间复杂度：O O(n n2 2)空间复杂度：空间复杂度：空间复杂度：空间复杂度：O O(1)(1)不稳定不稳定不稳定不稳定 第19页，共45页，编辑于2022年，星

31、期六锦标赛排序锦标赛排序 前提：前提：若乙胜丙，甲胜乙，则认为甲必能胜丙。若乙胜丙，甲胜乙，则认为甲必能胜丙。Zhao Cha Liu Bao Diao Yang Xue Wang Cha Bao Diao Wang Bao Diao Bao Liu Cha Cha Bao Cha Zhao Liu Diao Diao Yang Wang Liu Liu Zhao Wang Wang Xue Xue Xue Xue Yang Yang Yang Zhao 选出冠军的比较次数为选出冠军的比较次数为 22+21+20=23-1=n-1。选出亚军的比较次数为选出亚军的比较次数为 3，即，即 log2

32、n 次。次。其后的其后的 n 2 个人的名次均如此产生，所以对于个人的名次均如此产生，所以对于 n 个参赛选手个参赛选手 来说，即对来说，即对 n 个记录进行锦标赛排序，总的关键字比较次数至多个记录进行锦标赛排序，总的关键字比较次数至多 为为 (n 1)log2n n 1，故，故时间复杂度为：时间复杂度为：时间复杂度为：时间复杂度为：O O(n nloglog2 2n n)。此法除排序结果所需的此法除排序结果所需的 n 个单元外，尚需个单元外，尚需 n-1 个辅助单元。个辅助单元。4 4第20页，共45页，编辑于2022年，星期六10.4.2 树形选择排序树形选择排序 思想：思想：首先对首先对

33、 n 个记录的关键字进行两两比较，然后在其中个记录的关键字进行两两比较，然后在其中 n/2 个较小者之间再进行两两比较，直到选出最小关键字的记个较小者之间再进行两两比较，直到选出最小关键字的记 录为止。可以用一棵有录为止。可以用一棵有 n 个叶子结点的完全二叉树表示。个叶子结点的完全二叉树表示。38 13 13 13 38 65 27 13 38 49 65 97 76 27 49 13 76 27 27 27 49 49 38 38 49 49 49 49 65 49 49 76 65 65 97 97 76 97 76 97 13 27 38 49 49 65 76 97 时间复杂度：时间

34、复杂度：由于含有由于含有 n 个叶子结点的完全二叉树的深度为个叶子结点的完全二叉树的深度为 log2n+1，则在树形选择排序中中，除了最小关键字外，每选择，则在树形选择排序中中，除了最小关键字外，每选择 一个次小关键字仅需进行一个次小关键字仅需进行 log2n 次比较，故时间复杂度为次比较，故时间复杂度为 O(nlog2n)。缺点：缺点：1、与、与“”的比较多余；的比较多余；2、辅助空间使用多。、辅助空间使用多。第21页，共45页，编辑于2022年，星期六10.4.3 堆排序堆排序 堆的定义：堆的定义：n 个元素的序列个元素的序列(k1,k2,kn)，当且仅当满足下当且仅当满足下 列关系时，称

35、之为列关系时，称之为堆堆堆堆。或或(i=1,2,n/2)ki k2i ki k2i+1 ki k2iki k2i+1 小顶堆小顶堆 大顶堆大顶堆 小根堆小根堆 正正 堆堆 大根堆大根堆 逆逆 堆堆 第22页，共45页，编辑于2022年，星期六例例1：(96,83,27,38,11,09)例例2：(13,38,27,49,76,65,49,97)9627091138831327384965764997 可将堆序列看成完全二叉树，则：可将堆序列看成完全二叉树，则：k2i 是是 ki 的左孩子；的左孩子；k2i+1 是是 ki 的右孩子。的右孩子。所有非终端结点的值均不大（小）于其左右孩子结点的值。

36、所有非终端结点的值均不大（小）于其左右孩子结点的值。堆顶元素必为序列中堆顶元素必为序列中 n 个元素的最小值或最大值个元素的最小值或最大值。第23页，共45页，编辑于2022年，星期六 堆排序：堆排序：堆排序需解决的两个问题：堆排序需解决的两个问题：1、如何由一个无序序列建成一个堆？、如何由一个无序序列建成一个堆？2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？将无序序列建成一个堆将无序序列建成一个堆将无序序列建成一个堆将无序序列建成一个堆，得到关键字最小（大）的，得到关键字最小（大）的 记录；记录；输出堆顶的最小（大）值后，将剩余的输

37、出堆顶的最小（大）值后，将剩余的 n-1 个元个元 素重又建成一个堆素重又建成一个堆，则可得到，则可得到 n 个元素的次小值；如此个元素的次小值；如此 重复执行，重复执行，直到堆中只有一个记录为止，每个记录出堆直到堆中只有一个记录为止，每个记录出堆 的顺序就是一个有序序列的顺序就是一个有序序列，这个过程叫，这个过程叫堆排序。堆排序。第24页，共45页，编辑于2022年，星期六第二个问题解决方法第二个问题解决方法筛选：筛选：输出堆顶元素之后，以堆中最后一个元素替代之；然后将输出堆顶元素之后，以堆中最后一个元素替代之；然后将 根结点值与左、右子树的根结点值进行比较，并与其中小者进根结点值与左、右子

38、树的根结点值进行比较，并与其中小者进 行交换；重复上述操作，直至叶子结点，将得到新的堆，称这行交换；重复上述操作，直至叶子结点，将得到新的堆，称这 个从堆顶至叶子的调整过程为个从堆顶至叶子的调整过程为“筛选筛选筛选筛选”。132738496576499797972797499738979749656549764976979765762765493849971376 对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的次数所需进行的关键字比较的次数 至多为至多为 2(k-1)。第25页，共45页，编辑于2022年，星期六817364279812第一个问题解决方法：第一个问题解决方

39、法：从无序序列的第从无序序列的第 n/2 个元素（即无序序列对应的完全二叉个元素（即无序序列对应的完全二叉 树的最后一个内部结点）起，至第一个元素止，进行反复筛选。树的最后一个内部结点）起，至第一个元素止，进行反复筛选。建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。例例:排序之前的关键字序列为：排序之前的关键字序列为：40554936123673499881984940 现在，左现在，左/右子树都已经调整为堆，最后只要调整根结点，使右子树都已经调整为堆，最后只要调整根结点，使 整个二叉树是个整个二叉树是个“堆堆”即可。即可。817355第26页，共45页，编辑于202

40、2年，星期六堆排序的时间复杂度和空间复杂度：堆排序的时间复杂度和空间复杂度：1.对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的次数至多所需进行的关键字比较的次数至多 2.为为 2(k-1)；3.调整调整“堆顶堆顶”n-1 次，总共进行的关键字比较的次数不超过次，总共进行的关键字比较的次数不超过 2(log2(n-1)+log2(n-2)+log22)2n(log2n)因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为 O(nlogn)，与简单选择排序，与简单选择排序 O(n2)相比时间效率提高了很多。相比时间效率提高了很多。2.对对 n 个关键字，建成深度为个关键字，建

41、成深度为 h(=log2n+1)的堆，的堆，所需进行所需进行的的 关键字比较的次数至多关键字比较的次数至多 4n；空间复杂度：空间复杂度：S(n)=O(1)堆排序是一种堆排序是一种速度快速度快速度快速度快且且省空间省空间省空间省空间的排序方法。的排序方法。不稳定。不稳定。不稳定。不稳定。5 5第27页，共45页，编辑于2022年，星期六10.5 归并排序归并排序 归并：归并：将两个或两个以上的有序表组合成一个新的有序表。将两个或两个以上的有序表组合成一个新的有序表。在内部排序中，通常采用的是在内部排序中，通常采用的是 2-2-路归并排序路归并排序路归并排序路归并排序。即：将两个位。即：将两个位

42、 置相邻的记录有序子序列归并为一个记录有序的序列。置相邻的记录有序子序列归并为一个记录有序的序列。初始关键字：初始关键字：49 38 65 97 76 13 27 一趟归并后：一趟归并后：38 49 65 97 13 76 27 二趟归并后：二趟归并后：38 49 65 97 13 27 76 三趟归并后：三趟归并后：13 27 38 49 65 76 97 看成是看成是 n 个有序的子序个有序的子序 列（长度为列（长度为 1），然后），然后 两两归并。两两归并。得到得到 n/2 个长度为个长度为 2 或或 1 的有序子序列。的有序子序列。空间复杂度为：空间复杂度为：O(n)。时间复杂度为：时

43、间复杂度为：O(nlog2n)。稳定。稳定。第28页，共45页，编辑于2022年，星期六10.6 基数排序基数排序 基数排序是一种基于多关键字排序的思想，是将单关键字按基数排序是一种基于多关键字排序的思想，是将单关键字按 基数分成基数分成“多关键字多关键字”进行排序的方法。进行排序的方法。10.6.1 多关键字的排序多关键字的排序 例：例：将右表所示的学生将右表所示的学生 成绩单按数学成绩成绩单按数学成绩 的等级由高到低排的等级由高到低排 序，数学成绩相同序，数学成绩相同 的学生再按英语成的学生再按英语成 绩的高低等级排序。绩的高低等级排序。学号学号数学数学英语英语其它其它 101 B C 1

44、02 A B 103 C D 104 B B 105 A A 106 D B 107 E A 108 C B105 A A 102 A B 104 B B 101 B C 108 C B 103 C D 106 D B 107 E A特点：特点：每个记录最终的每个记录最终的 位置由两个关键位置由两个关键 字字 k1 k2 决定。决定。第二关键字第二关键字 K2 第一关键字第一关键字 K1 我们将它称之为我们将它称之为复复复复 合关键字合关键字合关键字合关键字，即，即多关键字多关键字 排序是按照复合关键字排序是按照复合关键字 的大小排序的大小排序。第29页，共45页，编辑于2022年，星期六例：

45、例：扑克牌中扑克牌中 52 张牌，可按张牌，可按花色花色花色花色和和面值面值面值面值分成两个分成两个“关键字关键字”，其，其 大小关系为：花色：大小关系为：花色：面值：面值：2345678910JQKA 若对扑克牌按花色、面值进行升序排序，得到如下序列：若对扑克牌按花色、面值进行升序排序，得到如下序列：2,3,.,A,2,3,.,A,2,3,.,A,2,3,.,A 即两张牌，若花色不同，不论面值怎样，花色低的那张牌小即两张牌，若花色不同，不论面值怎样，花色低的那张牌小 于花色高的，只有在同花色情况下，大小关系才由面值的大小确于花色高的，只有在同花色情况下，大小关系才由面值的大小确 定。这也是定

46、。这也是按照复合关键字的大小排序，按照复合关键字的大小排序，即：即：多关键字排序多关键字排序多关键字排序多关键字排序。第30页，共45页，编辑于2022年，星期六 多关键字排序的方法：多关键字排序的方法：n 个记录的序列个记录的序列 R1,R2,Rn 对关键字对关键字(Ki0,Ki1,Kid-1)有序是有序是指：对于序列中任意两个记录指：对于序列中任意两个记录 Ri 和和 Rj (1i jn)都满都满 足下列（词典）有序关系：足下列（词典）有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)其中：其中：K K 0 0 被称为被称为 最主位关键字最主位关键字最主位关键字最主位关

47、键字，K Kd d-1-1 被称为被称为最次位关键字最次位关键字最次位关键字最次位关键字。多关键字排序按照从最主位关键字到最次位关键字或从最次多关键字排序按照从最主位关键字到最次位关键字或从最次 位关键字到最主位关键字的顺序逐次排序，分两种方法：位关键字到最主位关键字的顺序逐次排序，分两种方法：最高位优先法，简称最高位优先法，简称 MSD 法：法：先按先按 k 0 排序分组，同一组中排序分组，同一组中 记录，关键字记录，关键字 k 0 相等，再对各组按相等，再对各组按 k 1 排序分成子组，之后，对排序分成子组，之后，对 后面的关键字继续这样的排序分组，直到按最次位关键字后面的关键字继续这样的

48、排序分组，直到按最次位关键字 k d 对对 各子组排序后，再将各组连接起来，便得到一个有序序列。各子组排序后，再将各组连接起来，便得到一个有序序列。第31页，共45页，编辑于2022年，星期六例例：先将学生记录按：先将学生记录按英语英语等级由高到低分成等级由高到低分成 A、B、C、D、E 五五 个组：个组：关键字类别关键字类别 ABCDE各组成员各组成员 AAABBCCDEABBCBDB学号学号数学数学英语英语其它其它 101 B C 102 A B 103 C D 104 B B 105 A A 106 D B 107 E A 108 C B 最低位优先法，简称最低位优先法，简称 LSD 法

49、：法：先从先从 k d-1 开始排序，再对开始排序，再对 k d-2 进行排序，依次重复，直到对进行排序，依次重复，直到对 k 0 排序后便得到一个有序序列。排序后便得到一个有序序列。然后按从左向右，从上向下的顺序将然后按从左向右，从上向下的顺序将 它们收集起来得到关键字序列：它们收集起来得到关键字序列：AA，EA，AB，BB，CB，DB，BC，CD 第32页，共45页，编辑于2022年，星期六 再按数学成绩由高到低分成再按数学成绩由高到低分成 A、B、C、D、E 五个组：五个组：关键字类别关键字类别 ABCDE各组成员各组成员 AAABBCCDEABBCBDB关键字类别关键字类别 ABCDE

50、各组成员各组成员 AABBCBDBEAABBCCD 可以看出，这个关键字序列已经是有序的了。可以看出，这个关键字序列已经是有序的了。AAAA，ABAB，BBBB，BCBC，CBCB，CDCD，DBDB，EA EA 对每个关键字都是将整个序列按关键字分组，然后按顺序收对每个关键字都是将整个序列按关键字分组，然后按顺序收 集，显然集，显然LSD法，操作比较简单。法，操作比较简单。按从上向下，从左向按从上向下，从左向 右的顺序将其收集起右的顺序将其收集起 来得到关键字序列：来得到关键字序列：AA，EA，AB，BB，CB，DB，BC，CD 按从上向下，从左向按从上向下，从左向 右的顺序将其收集起右的顺