《《数据结构——C语言描述（第二版）》-王路群-电子教案 第九章 排序》由会员分享，可在线阅读，更多相关《《数据结构——C语言描述（第二版）》-王路群-电子教案 第九章 排序（33页珍藏版）》请在金锄头文库上搜索。
1、第九章 排序,教学要求 1掌握：理解排序的定义和各种排序方法的特点，并能加以灵活应用。 2掌握：各种方法的排序过程及其依据的原则。 3了解：各种排序方法的时间复杂度的分析方法。 4了解：排序方法“稳定”或“不稳定”的含义。,主要内容,9.1 插入排序 9.2 希尔排序 9.3 选择排序 9.4 堆排序 9.5 快速排序 9.6 归并排序 9.7 基数排序 9.8 外部排序 9.9 各种排序方法的比较 9.10实训,排序,排序（sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。 由于待排序的记录数量不同，使得排序过程
2、中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中对外存进行访问的排序过程。,9.1 插入排序,线性插入排序的基本思想是：第1遍，将初始文件中的记录R1看作有序子文件，将R2插入这个子文件中。若R2的关键字小于R1的关键字，则R2插在R1的前面，否则R2插在R1的后面。第2遍，将R3插入前面的两个记录的有序子文件中，得到3个记录的有序子文件。依此类推，继续进行下去，直到将Rn插入到前面的n-1个记录的有序子文件中，最后得到n个记录的有序文件。,线
3、性插入排序的基本思想是：第1遍，将初始文件中的记录R1看作有序子文件，将R2插入这个子文件中。若R2的关键字小于R1的关键字，则R2插在R1的前面，否则R2插在R1的后面。第2遍，将R3插入前面的两个记录的有序子文件中，得到3个记录的有序子文件。依此类推，继续进行下去，直到将Rn插入到前面的n-1个记录的有序子文件中，最后得到n个记录的有序文件。图9-1所示为线性插入排序的例子。 为了避免检测是否应插在R1的前面，在R1的前面设立记录R0，它既是中间变量，又是监视哨。设（R1，R2，Ri-1）是已排序的有序子文件，则插入Ri的步骤是：首先将Ri存放到Ro中，然后将Ko（即原Ri的关键字Ki）依
4、次与Ki-1，Ki-2，比较，若KoKj（j=i-1，i-2，1），则Rj后移一个位置，否则停止比较和移动；最后，将Ro（即原来待插入的记录Ri）移到j+1的位置上。由于Ri的前面有监视哨Ro，因此不必每次判断下标j是否出界。算法描述如下：,void insertsort(struct node r n+1,int n) /* rn+1为一维数组，其中r0为监视哨，r1到rn为待排序的n个记录，排序好的记录仍放在r中*/ for(i=2;ir0.key) rj+1=rj; j-; rj+1=r0; ,折半插入排序,在线性插入排序中，我们采用顺序查找法来确定记录的插入位置。由于（R1，R2，Ri
5、-1）是有序子文件，我们可以采用折半查找法来确定R1的插入位置，这种排序称为折半插入排序。其算法可写出如下： void binarysort(struct node r n+1,int n) /*按关键字递增的次序对记录r1,r2,rn进行折半插入排序 */ for(i=2;i=l;j-) rj+1=rj; rl=r0; 在上面的算法中，每插入一个R1，平均比较次数为log2i。,9.2 希尔排序,希尔排序（Shells Method）又称“缩小增量排序”（Diminishing Increment Sort），是由D.L.Shell在1959年提出来的。它的作法是：先取定一个小于n的整数d1
6、作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，到第二个增量d2d1重复上述分组和排序，直至所取的增量dt=1（dtdt-1d2d1），即所有记录放在同一组中进行直接插入排序为止。 先从一个具体的例子来看希尔排序。假设待排序文件有10个记录，其关键字分别是：49，38，65，97，76，13，27，49/，55，04。增量序列取值依次为：5，3，1。 第一趟排序时，d1=5，整个文件被分成5组：（R1，R6），（R2，R7），（R5，R10）各组中的第1个记录都自成一个有序区，我们依次将各组的第2个记录R6，R7，R10分
7、别插入到各组的有序区中，使文件的各组均是有序的，其结果见图9-2的第七行。 第二趟排序时，d2=3，整个文件分成三组：（R1，R4，R7，R10），（R2，R5，R8），（R3，R6，R9），各组的第1个记录仍自成一个有序区，然后依次将各组的第2个记录R4，R5，R6分别插入到该组的当前有序区中，使得（R1，R4），（R2，R5），（R3，R6）均变为新的有序区，接着依次将各组的第3个记录R7，R8，R9分别插入到该组当前的有序区中，又使得（R1，R4，R7），（R2，R5，R8），（R3，R6，R9）均变为新的有序区，最后将R10插入到有序区（R1，R4，R7）中就得到第二趟排序结果。 最后
8、一趟排序时，d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。,若不设置监视哨，根据上例的分析不难写出希尔排序算法，请读者自行完成之。下面我们先分析如何设置监视哨，然后给出具体算法。设某一趟希尔排序的增量为h，则整个文件被分成h组：（R1，Rh+1，R2h+1，），（R2，Rh+2，R2h+2，），（Rh，R2h，R3h，），因为各组中记录之间的距离均为是h，故第1组至第h组的哨兵位置依次为1-h，2-h，0。如果象直接插入排序算法那样，将待插入记录Ri（h+1iN） 在查找插入位置之前保存到监视哨中，那么必须先计Ri属于哪一组，才能决定使用哪个监视哨来保存Ri。为了避免这种计算，我
9、们可以将Ri保存到另一个辅肋记录X中，而将所有监视哨R1-h，R2-h，R0的关键字，设置为小于文件中的任何关键字即可。因为增量是变化的，所以，各趟排序中所需的监视哨数目也不相同，但是我们可以按最大增量d1来设置监视哨。,rectype Rn+d1； /* Rd1-1为d1个监视哨*/ int dt； /* d0到dt-1为增量序列*/ SHELLSORT(R,d) Rectype R ； int d ； int i，j，k，h； rectype temp; int maxint=32767； /*机器中最大整数*/ for (i=0；id0；i+) Ri.key=-maxint； /*设置哨
10、兵*/ K=0； Do H=dk； /*取本趟增量*/ For(i=h+di；in+d1；i+) /*Rh+d1到Rn+d1-1插入当前有序区*/ temp=Ri； /*保存待插入记录Ri*/ j=i-h； while(temp.keyRj.key) /*查找正确的插入位置*/ Rj+h=Rj； /*后移记录*/ j=j-h； /*得到前一记录位置*/ Rj+h=temp； /*插入Ri*/ /*本趟排序完成*/ k+； while (h！=1)； /*增量为1排序后终止算法*/ /*SHELLSORT*/,读者可能看出，当增量h=1时，SHELLSORT算法与INSERTSORT基本一致。
11、对希尔排序的分析提出了许多困难的数学问题，特别是如何选择增量序列才能产生最好的排序效果，至今没有得到解决。希尔本为最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。后来又有人提出其它选择增量序列的方法，如di+1=(di-1)/3，dt=1，t=log3n-1；以及di+1=(di-1)/2，dt=1，t=log2n-1。 为什么希尔排序的时间性能优于直接插入排序呢？我们知道直接插入排序在文件初态为正序时所需要时间最少，实际上，当文件初基本有序时直接插入排序所需的比较和移动次数均较少。另一面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时
12、间复杂度O(n2)差别不大。在希尔排序时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较近于有序状态，所以新的国趟排序过程也较快。因此，希尔排序在较率上较直接接入排序有较大的改进。 希尔排序是不稳定的。参见图9-2的例子，该例中两个相同关键字49在排序前后的相对次序发生了变化。,9.3 选择排序,选择排序（selection sort）也是一种简单排序法。一个记录最多只需进行一次交换就可以直接到达它的排序位置。 设待排序的文件为（R1，R2，Rn），进行选择排序的基本步骤如下
13、： （1）置i 为1； （2）当in时，重复下列步骤； 1）当(Ri，Rn)中选出一个关键字最小的记录Rmin，若Rmin不是Ri，即Rmini则交换Ri和Rmin的位置；否则，不进行交换。 2）i的值加1。 第1遍扫描时，在n个记录中为了选出最小关键字的记录，需要进行n-1次比较，第2扫描时，在余下的n-1记录中，再选出具有最小关键字的记录需要比较n-2次，第n-1扫描时，在最后的2个记录中，比较1次选出最小关键字的记录。,9.4 堆排序,堆排序(heap sort)是在选择排序的基础上发展起来的。它比选择排序的效率要高。在堆排序中，把待排序的文件逻辑上看作是一棵顺序二叉树，并用到堆的概念。
14、在介绍堆排序之前，先引入堆的概念。 我们回忆一下，一棵有n个结点的顺序二叉树可以用一个长度为n的向量(一维数组)来表示；反过来，一个有n个记录的顺序表示的文件，在概念上可以看作是一棵有n个结点(即记录)的顺序二叉树。例如，一个顺序表示的文件(R1，R2，R9)，可以看作为图9-4所示的顺序二叉树。,当我们把顺序表示的文件(R1，R2，Rn)看作为顺序二叉树时，由顺序二叉树的性质可知：记录Ri(1n，则Ri的左孩子不存在；Ri的右孩子是记录R2i+1(2i+1n)，但若2i+1n，则Ri的右孩子不存在。 什么是堆呢?堆是一个具有这样性质的顺序二叉树，每个非终端结点(记录)的关键字大于等于它的孩子
15、结点的关键字。例如，图9-5所示的顺序二叉树就是一个堆。 显然，在一个堆中，根结点具有最大值(指关键字，下同)，而且堆中任何一个结点的非空左、右子树都是一个堆，它的根结点到任一叶子的每条路径上的结点都是递减有序的。 堆排序的基本思想是：首先把待排序的顺序表示(一维数组)的文件(R1，R2，Rn)在概念上看作一棵顺序二叉树，并将它转换成一个堆。这时，根结点具有最大值，删去根结点，然后将剩下的结点重新调整为一个堆。反复进行下去，直到只剩下一个结点为止。 堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆。初始状态时，结点是随机排列的，需要经过多次调整才能把它转换成一个堆，这个堆叫做初始堆。建成堆之后，交换根结点和堆的最后一个结点的位置，相当于删去了根结点。同时，剩下的结点(除原堆中的根结点)又构成一棵顺序二叉树。这时，根结点的左、右子树显然仍都是一个堆，它们的根结点具有最大值(除上面删去的原堆中的根结点)。把这样一棵左、右子树均是堆的顺序二叉树调整为新堆，是很容易实现的。 例如，对于图7-7所示的堆，交换根结点63和最后的结点30之后，便得到图9-6(a)所示的顺序二叉树(除63之外)。现在，新的根结点是30，其
