数据结构课件

数据结构第8章排序1数据结构电子教案第8章排序数据结构第8章排序1数据结构电子教案第8章排数据结构第8章排序2内容提要在当今社会中，人们经常要在浩如烟海的信息中查找某条信息。为了提高查找效率，就必须按某种合理的次序存储信息。假如图书馆的书籍和文献资料不是分门别类存储的，那么我们怎能迅速找到自己所需要的资料呢？假如英文字典不是按字母顺序排列词条的，那么我们怎能迅速查找某个单词呢？假如电话号码不是按照某种规律组织的，那么我们怎能迅速找到某个单位或个人的电话号码呢？本章所介绍的排序（Sorting又称分类）正是这样一种操作，它将要处理的信息，按照一定的规律重新排列使之有序。数据结构第8章排序2内容提要在当今社会中，人们数据结构第8章排序3内容提要在应用软件设计中，排序占有重要的地位。在实际的软件系统中，最常用且效率较高的内排序算法有5类：插入排序、选择排序、交换排序、归并排序和分配排序。本章将详细介绍插入排序、选择排序、交换排序和归并排序这几种内排序算法的基本思想、排序过程及实现算法。排序所需的时间占整个计算机系统运行时间的比重是很可观的。因此，熟悉各种排序方法，掌握算法设计的某些重要原则和技巧，对提高计算机数据处理系统的工作效率是很重要的。数据结构第8章排序3内容提要在应用软件设计中，数据结构第8章排序4第8章排序8.1排序的基本概念 8.2插入排序 8.3交换排序 8.4选择排序 8.5归并排序 8.6各种内排序方法的比较和选择 8.7排序的简单应用举例 本章小结 习题8数据结构第8章排序4第8章排序8.1排数据结构第8章排序5数据结构第8章排序5数据结构第8章排序68.1排序的基本概念排序是计算机软件设计中一项重要的技术，是计算机数据处理领域中最常用的一种运算。排序就是将一组杂乱无章的数据按规定的次序重新排列起来。排序的目的之一就是方便数据的查找。在日常工作中通过排序方便查找的例子是屡见不鲜的。例如，学生成绩的排名，高考成绩的统计，运动会中所有项目成绩的排名，英文字典中单词按字母的顺序排列，图书目录的编排顺序，电话号码簿按单位分类或按个人姓氏分类的顺序排列，职工档案信息的分类管理，仓库物资的分类管理等。对于经常要在计算机上查找的信息和存储对象，人们都会根据一定的规律对其进行排序或分类，以便提高查找效率。

数据结构第8章排序68.1排序的基本概念排数据结构第8章排序71．排序排序（Sorting）就是整理文件中的记录，将一组杂乱无章的的数据按关键字递增（或递减）的次序重新排列，使之成为一个有序序列的过程。例如，有10个记录的无序文件，其排序前后记录及其对应的关键字如下：数据结构第8章排序71．排序排序（Sortin数据结构第8章排序8可见，排序后关键字最小的记录R7排在序列的最前面，关键字最大的记录R3排在序列最后面。排序后整个序列按记录关键字从小到大顺序排列组成为一个有序文件。数据结构第8章排序8数据结构第8章排序92．关键字（Key）假设被排序的对象是由若干个记录组成的文件，而记录则由若干个数据项组成，其中可用来惟一标识一个记录的数据项，称为关键字项，该数据项的值称为关键字（key）。在文件中能够惟一区别一个记录的关键字称为主关键字；不同记录，其关键字值可能相同的关键字称为次关键字。关键字也称为关键码或排序码。数据结构第8章排序92．关键字（Key）假数据结构第8章排序10例如，表8.1就是一个学生成绩文件。每个学生是一个记录，而每个记录则由学生证号、姓名、各科成绩和总分数据项组成。其中，学生证号是能够惟一地区别一个学生记录的数据项，是学生记录主关键字，而其他数据项则是次关键字。表8.1学生成绩登记表数据结构第8章排序10例如，表8.1就是一个学数据结构第8章排序11表8.1学生成绩登记表数据结构第8章排序11表8.1学生成绩登记数据结构第8章排序12关键字可用来作为排序运算的依据。选取记录中的哪一项作为排序的关键字（或排序码），应根据问题的要求而定。例如，若将成绩登记表按学生证号排列，主关键字“学生证号”就是当前的排序码，见表8.1；若按学生的成绩总分排名次，次关键字“总分”就是当前的排序码，见表8.2。数据结构第8章排序12关键字可用来作为排序运算数据结构第8章排序13表8.2学生成绩统计表数据结构第8章排序13表8.2学生成绩统计数据结构第8章排序14一组记录按关键字递增或递减次序排列所得到的结果称为有序表，相应地，排序前的状态称为无序表。递增的次序又称为升序或正序，递减的次序又称为降序、逆序或反序。若有序表是按关键字升序排列的称为升序表或正序表；若按相反次序排列，则称为降序表或逆序表。数据结构第8章排序14一组记录按关键字递增或递数据结构第8章排序15

3．排序的稳定性与不稳定性排序算法的稳定性是衡量排序方法好坏的一个重要标准。任何排序算法，若使用主关键字进行排序，则排序结果一定是相同的；若排序算法使用次关键字排序，则排序结果有可能相同，有可能不同。假设n个待排序的序列中存在多个记录具有相同的次关键字值Ki（Ki表示第i个记录的关键字，i=1,2,…,n1,n），若Ki=Kj（j=1,2,…,n1,n,且ji），且排序前记录Ri排在记录Rj之前。若采用的排序方法，使排序后的记录Ri仍然排在记录Rj的前面，则称此排序方法是稳定排序，反之称此排序方法是不稳定排序。如上例中R4与R9的关键字K4=K9=30，排序后R4仍然在R9之前，所以上述排序方法是稳定的排序。数据结构第8章排序153．排序的稳定性与不稳数据结构第8章排序16

4．内部排序与外部排序排序的方法较多，可按不同的原则进行分类。按照排序过程所涉及的存储设备不同，排序可分为两大类：内部排序和外部排序（简称内排序和外排序）。内排序是指在整个排序过程中，数据全部存放在计算机的内存储器中，并且在内存中调整记录间的相对位置（即排序过程全部是在内存中进行的）。外排序是指在排序过程中，大部分数据存放在外存储器中，借助内存逐步调整记录之间的相对位置。数据结构第8章排序164．内部排序与外部排序数据结构第8章排序17显然，外排序速度比内排序速度要慢得多。内排序适用于记录个数不多的小文件，外排序则适用于记录个数比较多，不能一次将全部记录装入内存的大文件。内排序方法很多，按所用的策略不同，可以分为5类：插入排序、选择排序、交换排序、归并排序和分配排序（分配排序本书略去）。内排序是外排序的基础，外排序算法的原理与内排序算法的原理很多都是相同的，但具体实现的函数差别很大。限于篇幅，本书仅讨论几种典型的内排序算法，不讨论外排序算法，有兴趣的读者可参考相关书籍。

数据结构第8章排序17显然，外排序速度比内排序数据结构第8章排序185．排序方法的评价标准评价排序算法好与坏的标准主要有两条：排序算法的时间复杂度和空间复杂度。时间复杂度是指执行排序算法所耗费的时间。排序的时间主要耗费在数据比较与数据移动上，因此，排序算法的时间复杂度可用排序过程中数据的比较次数和数据的移动次数来衡量。如果关键字是字符串，数据的比较次数就是影响执行时间的主要因素。当记录个数很多时，数据的交换次数则是影响执行时间的另一个主要因素。一般情况下，排序算法的时间复杂度是按平均情况进行估计的，但有时也按最好的情况和最坏的情况进行估算。数据结构第8章排序185．排序方法的评价数据结构第8章排序19空间复杂度是指执行排序算法所需要的附加存储空间。当排序算法中使用的辅助存储单元与排序对象的个数无关时，其空间复杂度为O(1)。空间复杂度为O(1)的排序算法亦称为原地排序算法。原地排序算法就是利用原来存放记录的数组空间来重新按关键字大小存储记录的。此外，排序算法的稳定性和简单性也是衡量一个排序算法好与坏的重要指标。数据结构第8章排序19空间复杂度是指执行排序算数据结构第8章排序206．排序算法的存储实现每种排序算法可在不同的存储结构上实现。通常采用以下3种存储结构：①采用顺序表（即一维数组）作为存储结构：排序过程就是对记录本身进行物理重排的过程，即通过记录关键字的比较和移动，将记录移动到合适的位置上。②采用链表作为存储结构：排序过程中不需要移动记录，仅修改指针即可。③采用辅助表作为存储结构：有些排序方法难以在链表上实现，为了避免在排序过程中移动记录，可以为文件另外建立一个辅助表，例如，建立一个由记录关键字和指向记录的指针组成的索引表。这样，在排序过程中只需对这个辅助表的表目进行物理重排，即只移动辅助表的表目而不移动记录本身。数据结构第8章排序206．排序算法的存储实数据结构第8章排序21采用顺序表作为文件的存储结构时,其存储类型说明如下：#defineMAX400/*MAX为记录数组最大数*/typedefintdatatype;/*定义关键字类型*/typedefstructrecord/*定义记录为结构类型*/{intkey;/*记录的关键字域*/datatypeother;/*记录的其他域*/}rectype*s1,r[MAX]; /*r[MAX]数组存放原始数据，*s1存放排序后的数据*/注意：若不特别说明，本章所讨论的排序算法均采用顺序表作为文件的存储结构，并且按关键字递增排序。数据结构第8章排序21采用顺序表作为文件的存储数据结构第8章排序22第8章排序8.2插入排序

8.2.1直接插入排序

8.2.2希尔排序

数据结构第8章排序22第8章排序8.2数据结构第8章排序238.2插入排序插入排序类似于玩纸牌时整理手中纸牌的过程。插入排序的基本方法是：每次将一个待排序的记录按其关键字大小，插到前面已排好的序列中的适当位置，直到全部记录插入为止。常用的插入排序方法有：直接插入排序折半插入排序表插入排序希尔排序数据结构第8章排序238.2插入排序插入排数据结构第8章排序248.2.1直接插入排序1、直接插入排序的基本思想把数组R[n]中待排序的n个元素看成为一个有序表和一个无序表，开始时有序表只有一个元素R[1]，而无序表中包含有n1个元素R[2]～R[n]。排序过程中，每次取出无序表中第一个元素，将它插到有序表的适当位置上，使之成为新的有序表，这样经过n1次插入后，无序表变成为空表，而有序表包含有n个元素，至此排序完毕。数据结构第8章排序248.2.1直接插入排数据结构第8章排序25【例8.1】假设数组R有8个待排序的记录，它们的关键字分别为：【解】在直接插入排序的过程中，我们将一个记录的插入过程称为一趟排序（或一次排序）。直接插入排序每趟排序的具体过程如图8.1所示。其中，方括号表示有序表，圆括号表示监视哨，带方框的关键字表示下一趟排序过程中要插入的关键字。为了区别两个相同的关键字36，我们在后一个关键字36的下方加了一个下划线以示区别。第0趟表示原始关键字序列。数据结构第8章排序25【例8.1】假设数组R有数据结构第8章排序26图8.1直接插入排序过程示例数据结构第8章排序26图8.1直接插入排序数据结构第8章排序27insert_sort(r)/*直接插入排序*/rectyper[];{inti,j,n=NUM;/*NUM为实际输入的记录数*/for(i=1;i<=n;i++)/*i<=NUM条件很重要*/ {r[0]=r[i];/*R[0]是监视哨*/j=i-1; /*依次插入记录R[1],…,R[NUM]*/while(r[0].key<r[j].key)/*查找R[i]合适插入位置*/r[j+1]=r[j--];/*将大于R[i].key记录后移*/r[j+1]=r[0]; /*将R[i]插到有序表合适位置上*/}}/*INSERTSORT*//*直接插入排序—对数组R按递增顺序进行插入排序算法*/数据结构第8章排序27insert_sort(数据结构第8章排序28上述算法中记录R[0]有两个作用：一是在进入查找循环之前，它保存了R[i]的值，使得不致因记录的后移而丢失R[i]的内容；二是在while循环中“监视”下标变量j是否越界，一旦越界（即j＜0），R[0]将自动控制while循环的结束，从而避免了在while循环中每一次都要检测j是否越界（即省略了循环条件j≥1）。因此，R[0]也称为“监视哨”。采用这种程序设计技巧，使得循环条件的测试时间大约减少一半，而对于记录数较大的文件，节省的时间更加相当可观，希望能够掌握这种程序设计技巧。

数据结构第8章排序28上述算法中记录R[0]有数据结构第8章排序29【算法分析】直接插入排序算法时间复杂度可分最好、最坏和平均三种情况来考虑。（1）直接插入排序算法是由两重循环组成的，对于由n个记录组成的文件，外循环表示要进行插入排序的趟数，内循环表示完成一趟排序所要进行的记录关键字之间的比较和记录的后移。数据结构第8章排序29【算法分析】直接插入排序数据结构第8章排序30当参加排序的记录关键字已按升序排列时，这是最好的情况。在这种情况下，每趟排序过程中，while语句的循环次数为0，仅需进行一次关键字的比较，且无须后移记录。但是，在进入while循环之前，将R[i]保存到监视哨R[0]中需移动一次记录，在该循环结束之后，将监视哨R[i]插到R[j+1]中也需移动一次记录。因此，每趟排序过程中，关键字比较次数为1，记录的移动次数为2。整个排序过程中，关键字总的比较次数最小值Cmin和记录总的移动次数最小值Mmin为：数据结构第8章排序30当参加排序的记录关键字已数据结构第8章排序31（2）当参加排序的记录关键字按逆序排列时，这是最坏的情况。在这种情况下，第i趟排序过程中，while语句的循环次数为i，有序区中所有i-1个记录均向后移动一个位置，再加上while循环前后的两次移动，因此，在每趟排序过程中，关键字的比较次数为i，记录的移动次数为i-1+2。那么整个排序过程中，关键字总的比较次数的最大值Cmax和记录移动次数最大值Mmax为：数据结构第8章排序31（2）当参加排序的记录关数据结构第8章排序32（3）在平均情况下，参加排序的原始记录关键字是随机排列的。我们可取上述最小值和最大值的平均值，作为直接插入排序所需的平均比较次数和平均移动次数。因为第i趟排序过程中，关键字的平均比较次数为(1+i)/2，记录的平均移动次数为(i+3)/2，因此，对于n个记录进行直接插入排序时，总共需要进行n-1趟排序才能完成排序运算，其关键字的平均比较次数Cavg和记录的平均移动次数Mavg为：数据结构第8章排序32（3）在平均情况下，参加数据结构第8章排序33直接插入排序算法的时间复杂度为O(n2)。直接插入排序所需的辅助空间是一个监视哨，其作用是暂时存放待插入的元素，故空间复杂度为O(1)。直接插入排序是稳定的排序方法。直接插入排序的算法简单，容易实现。当记录数n很大时，不适合进行直接插入排序。数据结构第8章排序33直接插入排序算法的时间复数据结构第8章排序348.2.2希尔排序希尔排序基本思想是：不断把待排序的记录分成若干个小组，然后对同一组内的记录进行排序。在分组时，始终保证当前组内的记录个数超过前面分组排序时组内的记录个数。数据结构第8章排序348.2.2希尔排序数据结构第8章排序35希尔排序的过程如下：①以d1（0＜d1＜n1）为步长（增量），把数组R中的n个元素分为d1个小组，将所有下标距离为d1的记录放在同一组中。②对每个组内的记录分别进行直接插入排序。这样一次分组排序过程称为一次排序。③以d2（d1＞d2）为步长（增量），重复上述步骤，直到di=1，把所有n个元素放在一个组内，进行直接插入排序为止。该次排序结束时，整个序列的排序工作完成。数据结构第8章排序35希尔排序的过程如下：数据结构第8章排序36希尔排序实际上是对直接插入排序的一种改进。通过分析直接插入排序算法可知，如果待排序的原始序列越接近有序或者记录个数越少，则直接插入排序算法的时间效率就越高。希尔排序正是基于这两点考虑的。在希尔排序中，开始增量比较大，分组较多，每个组内记录个数较少，因而记录的比较次数和移动次数都比较少，在小组内用直接插入排序的时间效率很高。尽管增量逐渐变小，分组较少，每个组内记录个数逐渐增多，但同时记录越来越接近有序，因而记录的比较次数和移动次数越来越少，从而使直接插入排序的时间效率越来越高。数据结构第8章排序36希尔排序实际上是对直接插数据结构第8章排序37在希尔排序中，增量序列的选取到目前为止尚未得到一个最佳值，但最后一次排序时的增量值必须为1。一般选取增量序列的规则是：取di+1为di/3～di/2之间的数。最简单的方法是取di+1=di/2。注意：在一次分组排序过程中，可用直接插入排序算法对组内记录进行排序，也可采用其他合适的排序算法进行组内的排序。数据结构第8章排序37在希尔排序中，增量序列的数据结构第8章排序38【例8.2】假设数组R有12个待排序的记录，它们的关键字分别为：(65,34,25,87,12,38,56,46,14,77,92,23)

用希尔排序方法进行排序，请给出排序过程。【解】希尔排序的过程如图8.2所示。在图中，同一连线上关键字表明它们所属的记录是放在同一个组中的。由于数组待排序的记录数n=12，若按di+1=di/2选取增量序列，那么所得到的增量序列为：d1=n/2=12/2=6，d2=d1/2=6/2=3，d3=d2/2=3/2=1。数据结构第8章排序38【例8.2】假设数组R有数据结构第8章排序39图8.2希尔排序过程示意图数据结构第8章排序39图8.2希尔排序过程数据结构第8章排序40第1次希尔排序时，取增量d1=n/2=6，则所有记录被分为6组，它们分别是（R1,R7），（R2,R8），（R3,R9），（R4,R10），（R5,R11）和（R6,R12），对各组内的记录进行排序，得到一个新的结果序列1，如图8.2（a）所示。第2次希尔排序时，取增量d2=d1/2=3，将第1次排序后所得到的结果序列中所有位置距离为3的记录分成一组，共有三组（R1,R4.,R7,R10），（R2,R5,R8,R11）和（R3,R6,R9,R12），分别对这三个组内的记录进行一次排序，又得到新的结果序列2，如图8.2（b）所示。第3次希尔排序时，取增量d3=d2/2=1，这时序列中的所有记录都放在同一个组中。对该组中的记录进行排序，所得到的结果序列就是希尔排序后的有序序列，如图8.2（c）所示。数据结构第8章排序40第1次希尔排序时，取增量数据结构第8章排序41/*希尔排序——取增量为di+1=di/2的希尔排序-1*/shell_sort(r)rectyper[];{inti,n,jump,change,temp,m;/*change为交换标志，jump为增量步长*/jump=NUM;n=NUM;/*NUM为顺序表的实际长度*/while(jump>0){jump=jump/2;/*取步长di+1=di/2*/do{change=0;/*change=0表示未交换*/for(i=1;I<=n-jump;i++){m=i+jump;

数据结构第8章排序41/*希尔排序——取增量数据结构第8章排序42

/*希尔排序——取增量为di+1=di/2的希尔排序-2*/if(r[i].key>r[m].key) {temp=r[m].key;r[m].key=r[i].key;r[i].key=temp;change=1;/*change=1表示有交换*/

}/*if*/}/*for*//*本趟排序完成*/}while(change==1);/*当change=0时终止本趟排序*/}/*while*//*当jump=1且change=0时终止*/}/*SHELLSORT*/数据结构第8章排序42数据结构第8章排序43【算法分析】希尔排序比直接插入排序速度快。但希尔排序算法的时间复杂度分析比较复杂，排序实际所需的时间取决于各次排序时增量的个数和增量的取值。大量研究证明，若增量序列的取值比较合理，希尔排序算法的时间复杂度在O(nlog2n)～O(n2)之间，大致为O(n1.5)。希尔排序算法的空间复杂度为O(1)。由于希尔排序是按增量分组进行排序的，所以希尔排序是一种不稳定的排序方法。数据结构第8章排序43【算法分析】希尔排序比直数据结构第8章排序44第8章排序8.3交换排序

8.3.1冒泡排序

8.3.2快速排序 数据结构第8章排序44第8章排序数据结构第8章排序458.3交换排序利用交换记录位置进行排序方法称为交换排序。交换排序的基本思想是：两两比较待排序记录的关键字，若发现两个记录关键字的次序相反时即进行交换，直到没有反序的记录为止。交换排序的特点是：通过记录的交换将关键字较大的记录向文件的尾部移动，而将关键字较小的记录向文件的前部移动。本节将介绍两种常用的交换排序：冒泡排序和快速排序。数据结构第8章排序458.3交换排序利用交数据结构第8章排序468.3.1冒泡排序冒泡排序的基本思想是：将待排序的记录排列成一个垂直的序列，而不是一个水平的序列。把记录想象成水箱里的气泡，其关键字相当于气泡的重量。对所有待排序的记录扫描一趟以后，通过两个相邻记录之间的比较和交换，使得气泡下沉或上升到其重量应该到的最终位置上。注意：本节介绍的冒泡排序方法是每趟扫描以后，使得轻气泡上升到合适的位置上。数据结构第8章排序468.3.1冒泡排序冒数据结构第8章排序47冒泡排序的具体过程是：把第n个记录的关键字与第n1个记录的关键字进行比较，如果r[n].key＜r[n1].key，则交换两个记录r[n]和r[n1]的位置，否则不交换；然后再把第n1个记录的关键字与第n2个记录的关键字进行比较；其余类推，直到第2个记录与第1个记录的关键字比较完为止，这个过程就称为一趟冒泡排序。在整个冒泡排序过程中，首先对n个待排序的记录进行第一趟冒泡排序，将关键字最小的记录上浮到数组的第一个单元r[1]中；然后对剩下的n1个记录进行第二趟冒泡排序，使关键字次小的记录上浮到数组第二个单元r[2]中；重复进行n1趟后，轻者上浮而重者下沉，则整个冒泡排序结束。数据结构第8章排序47冒泡排序的具体过程是：把数据结构第8章排序48【例8.3】假设n=8，数组R中8个记录的关键字分别为：（53,36,48,36,60,17,18,41）用冒泡法进行排序，请给出排序的过程。【解】第一趟冒泡排序过程如图8.3所示，冒泡排序全部过程则如图8.4所示。在图8.4中，第一列为初始的关键字序列，从第二列起依次为各趟冒泡排序的结果，黑方括号括起来的记录为当前的无序区。数据结构第8章排序48【例8.3】假设n=8，数据结构第8章排序49图8.3第一趟冒泡排序过程示例数据结构第8章排序49图8.3第一趟冒泡排数据结构第8章排序50图8.4从下往上的冒泡排序全过程示意图数据结构第8章排序50图8.4从下往上的冒数据结构第8章排序51/*冒泡排序算法——从下往上扫描的冒泡排序*/bubble_sort(r) rectyper[];{inti,j,noswap=0,n=NUM;/*noswap为交换标志*/rectypetemp;for(i=1;i<n;i++)/*进行n-1趟冒泡排序*/{noswap=1;/*noswap=1表示没有记录交换*/for(j=n;j>=i;j--)/*从下往上扫描*/if(r[j].key<r[j-1].key)/*交换记录*/{temp.key=r[j-1].key;r[j-1].key=r[j].key;r[j].key=temp.key;

noswap=0;}/*if*/if(noswap)break;}/*for*/}/*BUBBLESORT*/数据结构第8章排序51/*冒泡排序算法——从数据结构第8章排序52算法说明从冒泡排序实例可以看出：对n个记录进行冒泡排序时，至多进行n1趟排序。如果本趟冒泡排序过程没有交换任何记录，则说明全部记录已经有序，排序就此结束。为此，在算法中设置一个标志变量noswap，用于判断本趟冒泡排序过程是否有记录交换。在每趟冒泡排序之前，置noswap=1；本趟排序过程中若交换记录，则置noswap=0；每趟冒泡排序之后，若noswap=1，则表明全部记录已经有序，算法可以就此终止。

数据结构第8章排序52算法说明数据结构第8章排序53【算法分析】冒泡排序的执行时间与待排序记录的原始状态有很大关系。若原始记录的初始状态是递减有序（即按“逆序”排列）的，这时需要进行n-1趟排序，每趟冒泡排序要进行n-i次关键字的比较（1≤i≤n-1），且每次比较都必须交换两个记录的位置，记录移动次数为3次。这是最坏的情况，此时关键字的比较次数Cmax和记录的移动次数Mmax均达到最大值为：因此，在最坏的情况下，冒泡排序的时间复杂度为O(n2)。数据结构第8章排序53【算法分析】冒泡排序的执数据结构第8章排序54若原始记录的初始状态是递增有序（即按“正序”排列）的，这时只需进行一趟冒泡排序过程就能结束排序。在排序过程中，记录关键字总的比较次数为n-1次，记录总的移动次数为0次。这是最好的情况，此时Cmin=n-1，Mmin=0，冒泡排序的时间复杂度为O(n)。在平均情况下，冒泡排序的比较次数和移动次数大约是最坏情况的一半。因此，冒泡排序算法的平均时间复杂度为O(n2)，冒泡排序算法的空间复杂度为O(1)。显然，冒泡排序算法是一种稳定的排序方法。在一般情况下，冒泡排序比直接插入排序和直接选择排序需要移动记录的次数多，所以它是这三种简单排序方法中速度最慢的一个。但是，当原始的记录序列为有序时，则冒泡排序又是三者中速度最快的一种排序方法。数据结构第8章排序54若原始记录的初始状态是递数据结构第8章排序558.3.2快速排序快速排序是一种交换排序，是对冒泡排序的改进，是目前所有排序方法中速度最快的一种。在冒泡排序中，记录的比较和交换是在相邻两个单元中进行的，记录每次的交换只能上移或者下移一个相邻位置，因而总的比较次数和移动次数比较多；而在快速排序中，记录的比较和移动从两端向中间进行，关键字大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离比较远，因而总的比较次数和移动次数比较少。数据结构第8章排序558.3.2快速排序快数据结构第8章排序56快速排序的基本思想是：在待排序的n个记录中任意选择一个记录作为标准记录（通常选第一个记录作为标准记录），以该记录的关键字为基准，将当前的无序区划分为左右两个较小的无序子区，使左边无序子区中各记录的关键字均小于基准记录的关键字，使右边无序子区中各记录的关键字均大于或等于基准记录的关键字，而标准记录则位于两个无序区的中间位置上（也就是该记录最终排序的位置上），分别对左右两个无序区继续进行上述的划分过程，直到无序区中所有的记录都排好序为止。在快速排序中，将待排序区间按照标准记录关键字分为左右两个无序区的过程称为一趟快速排序（或一次划分）。数据结构第8章排序56快速排序的基本思想是：在数据结构第8章排序57

【例8.4】假设n=8，数组R中8个记录的关键字分别为：（49,38,65,97,76,13,27,49）试给出其第一趟快速排序的划分过程和结果。

【解】若选取第一个记录作为标准记录temp，则快速排序第一次划分过程如图8.5所示。在图8.5中，方括号内为待排序的无序区。带方框和阴影的数据是标准记录temp的关键字49，在划分过程中它并没有真正进行交换，而是在划分结束时才将其放到正确的位置上。

数据结构第8章排序57【例8.4】假设n数据结构第8章排序58图8.5快速排序的一次划分过程示例数据结构第8章排序58图8.5快速排序的一数据结构第8章排序59显然，经过一次划分后，标准记录将整个无序区分成左右两个无序区，用同样的方法对左右两个无序区继续进行划分，直到各个子区间的长度为1时终止。图8.6是在快速排序执行过程中，每一次划分后关键字的排列情况，图中加阴影的记录为本次快速排序的基准记录。数据结构第8章排序59显然，经过一次划分后，标数据结构第8章排序60图8.6快速排序执行过程示例数据结构第8章排序60图8.6快速排序执行数据结构第8章排序61一趟快速排序的具体做法是：①将标准记录r[s]保存到临时变量temp中，temp=r[s]。②令j从n起向左扫描，将r[j].key与temp.key进行比较，直到找到第一个满足temp.key＞r[j].key条件的记录时停止，然后将r[j]移到r[i]的位置上。③令i从i+1起向右扫描，将r[i].key与temp.key进行比较，直到找到第一个满足temp.key<r[i].key记录时停止，然后将r[i]移到r[j]的位置上。④反复交替执行步骤②和步骤③，直到指针i和j指向同一个位置（即i=j）时为止，此时i就是标准记录temp最终存放的位置，因此将temp存放到r[i]单元就完成了一次划分过程。至此，一趟快速排序过程完成，数组被分成r[s..i1]和r[i+1..t]两个部分。数据结构第8章排序61一趟快速排序的具体做法是数据结构第8章排序62一次划分过程及完整的快速排序算法如下：intpartition(r,s,t)/*快速排序算法中一趟划分函数*/rectyper[];/*返回划分后被定位基准记录位置*/ints,t; /*对无序区R[s]到R[t]进行划分*/{inti,j;rectypetemp;i=s;j=t;temp=r[i];/*初始化，temp为基准记录*/do{while((r[j].key>=tmp.key)&&(i<j))j--;

if(i<j)r[i++]=r[j]; /*交换R[i]和R[j]*/

while((r[i].key<=temp.key)&&(i<j))i++;

if(i<j)r[j--]=r[i]; /*交换R[i]和R[j]*/}while(i!=j); /*i=j，则一次划分结束*/

r[i]=temp;/*最后将基准记录temp定位*/return(i);}/*PARTITION*/数据结构第8章排序62一次划分过程及完整的快速数据结构第8章排序63/*快速排序算法——对R[hs]到R[ht]进行快速排序*/voidquick_sort(r,hs,ht)/*对R[hs]到R[ht]进行快速排序*/

rectyper[];inths,ht;{inti;if(hs<ht)/*只有一个或无记录时无须排序*/{i=partition(r,hs,ht);/*R[hs]到R[ht]一次划分*/

quick_sort(r,hs,i-1);/*递归处理左区间*/

quick_sort(r,i+1,ht);/*递归处理右区间*/}}/*QUICK_SORT*/数据结构第8章排序63/*快速排序算法——对数据结构第8章排序64【算法分析】在快速排序中，若把每一次划分用的标准记录作为根结点，把划分所得到的左区间和右区间看成是根结点的左子树和右子树，那么整个排序过程就对应着一棵具有n个结点的二叉排序树，所需划分的层数就等于所对应的二叉排序树的高度减1，所需划分的区间数就等于所对应的二叉排序树中的分支结点数。例如，图8.6的快速排序过程所对应的二叉排序树如图8.7所示。该树的高度为4，分支结点数为4，所以该排序过程需要进行3层划分，共包含4个划分区间。

数据结构第8章排序64【算法分析】在快速排序中数据结构第8章排序65图8.7快速排序所对应的二叉排序树数据结构第8章排序65图8.7快速排序所对数据结构第8章排序66快速排序算法的执行时间取决于标准记录的选择。如果每次排序时所选的标准记录值都是当前子序列的“中间数”，那么该记录排序的终止位置应该位于该子序列的中间，这样就把原来的子序列分解成两个长度基本相等的更小序列。在这种情况下，由快速排序过程所得到的二叉排序树是一棵理想平衡树，每次划分所得到的左区间和右区间的长度大致相等。由于理想平衡树的结点数n与高度h的关系为：

log2n＜h≤log2n+1所以快速排序总的比较次数应为

Cn≤(n+1)log2n数据结构第8章排序66快速排序算法的执行时间取数据结构第8章排序67通过上述分析可知，在最好的情况下，快速排序得到的是一棵理想平衡树，其算法的时间复杂度为O(nlog2n)。当n较大时，快速排序是目前为止速度最快的一种排序方法。在平均情况下，快速排序得到的是一棵随机的二叉排序树。算法平均时间复杂度是O(nlog2n)。但是，在最坏的情况下，若原始记录序列已经有序，且每次都选取第一个记录作为标准记录，则快速排序得到的二叉排序树退化成一棵单枝树，也称为“退化树”。数据结构第8章排序67通过上述分析可知，在最好数据结构第8章排序68图8.8正序记录所对应的二叉排序树数据结构第8章排序68图8.8正序记录所对数据结构第8章排序69例如，图8.8所示的二叉排序树就是对5个正序记录（1,2,3,4,5）进行快速排序得到的退化树。在这种情况下，快速排序必须进行n-1趟排序，而每趟排序过程中需要进行ni次比较，因此，总的比较次数达到最大值Cmax为：此时，快速排序退化为“慢速排序”，成为最差的排序方法，其算法的时间复杂度为Ｏ(n2)。数据结构第8章排序69例如，图8.8所示的二叉数据结构第8章排序70为了避免最坏的情况发生，可以在每次划分之前将当前区间的第一个元素、最后一个元素和中间一个元素值进行比较，选取三者中居中值作为标准记录并调换到第一个记录位置上；或者随机选择标准记录，然后执行一次划分过程。快速排序算法要用堆栈临时保存递归调用的参数，堆栈空间的使用个数由递归调用次数决定。在最好的情况下，快速排序算法的空间复杂度为O(log2n)；在最坏的情况下，快速排序算法要递归处理(n1)次，其空间复杂度为O(n)；在平均情况下，快速排序的空间复杂度为O(log2n)。快速排序是一种不稳定的排序方法。数据结构第8章排序70为了避免最坏的情况发生，数据结构第8章排序71第8章排序8.4选择排序 8.4.1直接选择排序 8.4.2堆排序 数据结构第8章排序71第8章排序数据结构第8章排序728.4选择排序选择排序的基本思想是：每一趟在ni+1（i=1,2,…,n1）个待排序记录中选取关键字最小的记录作为有序序列中第i个记录，直到全部记录排完为止。本节介绍两种选择排序方法：直接选择排序堆排序数据结构第8章排序728.4选择排序选择排数据结构第8章排序738.4.1直接选择排序直接选择排序的基本思想是：首先从所有待排序的记录中选出关键字最小的记录，将它与待排序的第一个记录互相交换位置；然后从去掉最小的关键字记录后剩余的记录中，再选出关键字最小的记录并将它与第二个记录交换位置；其余类推，直到所有记录都排完为止。数据结构第8章排序738.4.1直接选择排数据结构第8章排序74

【例8.5】假设n=8，数组R中8个记录关键字为：

（53,36,48,36,60,17,18,41）

若用直接选择法进行排序，请给出排序过程。

【解】图8.9是直接选择排序的过程示意图。在排序过程中，每次选择和交换记录后各关键字位置的变动情况如图所示，图中方括号表示待排序区间，它是一个无序表，圆括号则表示有序表。

数据结构第8章排序74【例8.5】假设n=数据结构第8章排序75图8.9直接选择排序的过程示例数据结构第8章排序75图8.9直接选择排序数据结构第8章排序76直接选择排序的算法如下：voidselect_sort(r)/*直接选择排序函数*/rectyper[];{rectypetemp;inti,j,k,n=NUM;/*NUM为实际输入记录数*/

for(i=1;i<=n;i++)/*做n-1趟选择排序*/{k=i;

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

if(r[j].key<r[k].key)k=j;

if(k!=i){temp=r[i];/*交换记录R[i]和R[k]*/r[i]=r[k];r[k]=temp;}}/*for*/}/*SELECTE_SORT*/数据结构第8章排序76直接选择排序的算法如下：数据结构第8章排序77【算法分析】在直接选择排序算法中，总共要进行n1趟选择和交换才能完成排序工作。直接选择排序的比较次数与记录关键字的初始状态无关。无论关键字的初始状态如何，每趟选择排序都要进行ni次比较，才能找出关键字最小的记录，即第一趟排序需要比较n1次，第二趟排序要比较n2次，……，第n1趟排序只要比较1次，所以关键字总的比较次数的最大值Cmax为：数据结构第8章排序77【算法分析】在直接选择排数据结构第8章排序78显然，记录的移动次数与记录关键字的初始状态有关。在最好的情况下，其初始的记录关键字为正序，每趟排序不用交换记录，记录移动次数为0次；在最坏的情况下，其初始的记录关键字为反序，每趟排序都要交换记录，记录移动次数为3次。因此，该算法总的移动次数最好时为Mmin=0最坏时为Mmax=3(n1)可见，直接选择排序总时间复杂度仍是O(n2)。直接选择排序只需要一个临时单元交换记录，因此，直接选择排序的空间复杂度为O(1)。直接选择排序是不稳定的排序方法。数据结构第8章排序78显然，记录的移动次数与记数据结构第8章排序798.4.2

堆排序堆排序（HeapSort）是在直接选择排序方法的基础上借助于完全二叉树的结构而形成的一种排序方法。堆排序是完全二叉树顺序存储结构的应用。在直接选择排序中，为找出关键字最小的记录需要进行n1次比较，然后为找出关键字次小的记录要对剩下的n1个记录进行n2次比较。在这n2次比较中，有许多次比较已经在n1次的排序中做了。数据结构第8章排序798.4.2堆排序堆排数据结构第8章排序80事实上，直接选择排序的每次排序除了找到当前最小关键字外，还产生了许多比较信息，这些信息在以后各次排序中还有用，但由于没有保存这些信息，所以每次排序都要对剩下的记录关键字重新进行比较，这就大大增加了时间开销。堆排序就是针对直接选择排序所存在的上述问题的一种改进的排序方法，也就是在寻找当前最小关键字的同时，将本次排序过程所产生的其他比较信息保存起来。数据结构第8章排序80事实上，直接选择排序的每数据结构第8章排序811．堆的定义及堆与完全二叉树的关系假设n个元素的序列为{R1,R2,…,Rn}，其对应的关键字序列为{K1,K2,…,Kn}，若此关键字满足下列两个条件中任一个条件，则称此元素序列为堆。①

Ki

≤

K2i

且

Ki

≤

K2i+1（1≤i≤n/2）②

Ki

≥

K2i

且Ki

≥

K2i+1（1≤i≤n/2）数据结构第8章排序811．堆的定义及堆与完全二数据结构第8章排序82通常，我们将满足第一个条件的堆称为小根堆，将满足第二个条件的堆称为大根堆。以后若不特别说明，本节所讨论的堆均为大根堆。只要掌握好大根堆的处理方法，小根堆的情况可以仿照大根堆来进行处理。一个堆对应着一棵完全二叉树，树中每个编号为i的结点的值就是堆中下标为i的元素Ri。一棵完全二叉树成为堆的条件是：该树中每个非终端结点的值必然大于等于其左、右孩子结点的值。数据结构第8章排序82通常，我们将满足第一个条数据结构第8章排序83

堆具有以下两个性质：①堆是一棵顺序存储的具有特殊性质的完全二叉树，树中任一结点的关键字均大于其左、右孩子（若存在）结点的关键字。这棵完全二叉树的任一子树亦是堆。②在大根堆中，根结点的关键字是堆中最大者；在小根堆中，根结点的关键字是堆中最小者。我们将根结点称为堆顶元素。例如，关键字序列{75,38,62,15,26,49,58,17,6}和{10,15,50,25,30,80,76,38,49}满足堆的条件，分别为大根堆和小根堆，其对应的完全二叉树及顺序存储结构如图8.10所示。

数据结构第8章排序83堆具有以下两个性质：①数据结构第8章排序84图8.10堆对应的完全二叉树数据结构第8章排序84图8.10堆对应的完数据结构第8章排序852．初始堆的建立堆排序的关键是构造初始堆。堆的建立方法有多种，在此仅介绍用筛选法建立初始堆。我们知道，对于一棵具有n个结点的完全二叉树，若从1开始对树中结点编号，则编号为1～n/2的结点为分支结点，编号大于n/2的结点为叶结点。对于每个编号为i的分支结点，它的左孩子和右孩子结点的编号分别为2i和2i+1。除编号为1的根结点外，对于每个编号为i的结点，其双亲结点的编号均为i/2。数据结构第8章排序852．初始堆的建立堆排序的数据结构第8章排序86

筛选法建立初始堆的基本思想:首先，将待排序的记录序列按原始顺序存放到一棵完全二叉树的各个结点中。然后，根据堆的定义将完全二叉树中每个结点为根的子树都调整为堆。由于完全二叉树中所有编号为i＞n/2的叶结点Ki都没有孩子结点，以这些结点Ki为根的子树均已经是堆，因此，我们只需要从完全二叉树中编号最大的分支结点Ki开始，依次对i=n/2，n/21，n/22，…，1为根的分支结点Ki进行筛运算，以便形成以每个分支结点为根的堆。对树的根结点K1进行“筛选”后，则整个树就构成一个初始堆。数据结构第8章排序86筛选法建立初始堆的数据结构第8章排序87【例8.6】假设待排序的序列有10个记录，它们的关键字序列为：（45,36,18,53,72,30,48,93,15,36）要求用筛选法建立其初始堆，并给出建立初始堆的过程示意图。【解】用筛选法建立初始堆的过程如图8.11所示。由于结点数n=10，所以从编号为i=n/2=5的结点K5=72开始，到树的根结点时为止，依次对每个分支结点进行筛运算。图8.11（a）是按原始记录的关键字序列建立的完全二叉树，图8.11（b）～（f）是依次对每个分支结点进行筛运算的过程和结果，图8.11（f）是最后建成的初始堆。数据结构第8章排序87【例8.6】假设待排序的数据结构第8章排序88图8.11用筛选法建立初始堆的过程数据结构第8章排序88图8.11用筛选法建数据结构第8章排序89图8.11用筛选法建立初始堆的过程（续）数据结构第8章排序89图8.11用筛选法建数据结构第8章排序90筛运算的具体过程：以分支结点Ki为根结点，将根结点的关键字Ki与两个孩子中关键字较大者Kj（j=2i或j=2i+1）进行比较。若Ki≥Kj，说明以Ki为根的子树已构成堆，则筛运算结束；若Ki≤Kj，则将Ki与Kj互换位置；互换后若破坏了以Kj为根的堆，就继续将根结点Kj与新的孩子结点中关键字较大者进行比较，其余类推，直到Kj的关键字大于或等于两个孩子结点的关键字或者使其成为叶结点时为止。这样，以Ki为根的子树就构成一个堆。筛运算的过程就像过筛子一样，将较小的关键字逐层筛选下去，把最大的关键字逐层筛选上来，所以将建堆的过程形象地称为“筛运算”。数据结构第8章排序90筛运算的具体过程：数据结构第8章排序91

对R[i]进行筛运算的函数shift：shift(r,i,m)/*堆的筛选算法——在R[i]到R[m]中调整堆*/rectyper[];/*将R[i]为根的完全二叉树调整为堆*/inti,m;{intj;rectypetemp;temp=r[i];j=2*i;while(j<=m)/*j≤m,R[2*i]是R[i]的左孩子*/{if((j<m)&&(r[j].key<r[j+1].key)) j++;/*j指向R[i]左右孩子中关键字大者*/数据结构第8章排序91对R[i]进行筛运算数据结构第8章排序92

if(temp.key<r[j].key)/*若孩子关键字大于父结点*/{r[i]=r[j];/*将R[j]调到父亲结点的位置上*/i=j;/*修改i和j的值，以便继续“筛”结点*/j=2*i;}elsej=m+1;}/*调整完毕，退出循环*/r[i]=temp;/*将被筛选的结点放入正确的位置*/}/*SHIFT*/数据结构第8章排序92if(temp.数据结构第8章排序933．将删除堆顶元素后的完全二叉树重新调整为新堆如何将删除堆顶元素后的完全二叉树调整为新堆？由堆的性质可知，删除堆顶元素后，这棵完全二叉树除了根结点可能违反堆的性质外，其余任何结点为根的二叉树仍然是堆。因此，只需将树根结点由上至下“筛选”到某个合适的位置上，使其左、右孩子结点的值都小于它或者成为叶结点即可。当筛选工作结束时，新堆已经构成。数据结构第8章排序933．将删除堆顶元素后的完数据结构第8章排序94【例8.7】假设根据其关键字序列建立的初始堆如图8.12（a）所示，删除堆顶元素93后将其调整为新堆，请给出其调整过程。

【解】将堆顶元素93删除，并且重新调整堆的具体过程如图8.12（b）～（d）所示。数据结构第8章排序94【例8.7】假设根据其关数据结构第8章排序95图8.12删除堆顶元素93并重新调整堆的过程示意图数据结构第8章排序95图8.12删除堆顶元数据结构第8章排序96在例题8.7中，当删除堆顶元素

93后（假设此处删除操作是将堆顶元素与堆中最后一个元素交换），将堆中最后一个元素36放到堆顶位置，如图8.12(b)所示。由于不满足堆的条件，因此，接着对新的堆顶元素36进行筛选。因为堆顶元素36的左孩子值为72，右孩子值为48，所以将元素36与72互换，其结果如图8.12(c)所示。由于交换位置后，元素36的新左、右孩子值分别为53和45，仍然不能满足堆的条件，因此，继续将元素36与其左孩子53互换位置，其结果如图8.12(d)所示。经过这次交换后，元素36与其左孩子值36相等且大于其右孩子值15，显然已经满足堆的条件，此次筛选工作结束，新堆已经重新建立。数据结构第8章排序96在例题8.7中，当删除堆数据结构第8章排序974．堆排序堆排序是一种利用堆的特性进行排序的方法。堆排序的基本思想是：根据原始记录的关键字序列建立初始堆，使得堆顶元素是关键字最大的记录，然后删除堆顶元素并将其保存到数组中。继续调整剩余的记录关键字序列使之重新构成一个新堆，再删除堆顶元素得到关键字为次大的记录并将其保存到数组中；如此反复，直到堆中只有一个记录时为止。此时，数组中所有元素是一个按记录关键字从小到大顺序排列的有序序列。数据结构第8章排序974．堆排序堆排序是一种利数据结构第8章排序98实现堆排序要解决以下两个问题：①如何将原始记录序列建成一个堆，即建立初始堆？②如何将删除根结点后的完全二叉树重新调整为一个新堆？数据结构第8章排序98实现堆排序要解决以下两个数据结构第8章排序99

实现堆排序的具体过程如下：①将待排序的记录按顺序输入完全二叉树中，然后用筛选函数shift建立初始堆；②将堆顶元素R[1]与堆中最后一个元素R[n]互换，使R[n]成为最大关键字；③用筛选函数shift将树根结点R[1]继续“筛选”到合适的位置上，重新构成新堆；④重复上述步骤②～③，经过n1次交换和筛选后，就完成了堆排序。数据结构第8章排序99实现堆排序的具体过程数据结构第8章排序100堆排序算法的C语言描述如下：

voidheap_sort(r)/*对数组R[1]到R[NUM]进行堆排序*/rectyper[];{rectypetemp;inti,n;n=NUM;/*NUM为数组的实际长度*/for(i=n/2;I>1;i--)/*建立初始堆*/

shift(r,i,n);for(i=n;i>1;i--)/*进行n-1趟筛选、交换和调整*/{temp=r[1];/*将堆顶元素R[1]与最后一个元素交换*/r[1]=r[i];r[i]=temp;

shift(r,1,i-1)/*将元素R[1]到R[i-1]重新调整为堆*/}/*FOR*/}/*HEAP_SORT*/数据结构第8章排序100堆排序算法的C语言描述数据结构第8章排序101【例8.8】假设n=8，数组R中的关键字序列为（36,25,48,12,65,43,20,58），请用图形表示堆排序的全部过程。【解】图8.13所示是用图形表示堆排序全过程的示意图。图中虚线表示已经排好序的关键字。图8.13（a）所示是原始的关键字序列。图8.13（b）所示是以筛选法建成的初始堆。数据结构第8章排序101【例8.8】假设n=8数据结构第8章排序102【例8.8解续】图8.13（a）所示是原始的关键字序列。图8.13（b）所示是以筛选法建成的初始堆。初始堆建成后，将堆顶元素65和堆的最后一个元素12交换位置。由于除根结点外的其他结点为根的子树仍然为堆，所以用筛选法将根结点元素12调整成一个新堆即可。用筛选法调整后的堆顶元素为58，接着将堆顶元素与堆中倒数第二个元素20交换位置。如此反复进行下去，就完成了堆排序。数据结构第8章排序102【例8.8解续】数据结构第8章排序103图8.13堆排序过程的图形表示数据结构第8章排序103图8.13堆排序过数据结构第8章排序104图8.13堆排序过程的图形表示（续）数据结构第8章排序104图8.13堆排序过数据结构第8章排序105【例8.8解续】图8.14给出了构成初始堆和堆排序过程中，每次筛运算后数组R中各记录关键字的变动情况。图8.14（a）所示为构堆时数组R中每趟的变化情况；图8.14（b）中带方框的关键字表示已排序的关键字。数据结构第8章排序105【例8.8解续】数据结构第8章排序106图8.14堆排序的全过程中数组R的变化情况数据结构第8章排序106图8.14堆排序的数据结构第8章排序107【算法分析】堆排序的时间主要由建立初始堆的时间和不断调整重建新堆的时间这两部分构成。建立初始堆时，调用shift函数对每个非叶结点自上而下进行“筛选”，需要进行n/2次筛运算；重建新堆时，每次进行筛运算将根结点“下沉”到合适的位置上，需要进行n