《第八章排序(修订版本2010.6).doc》由会员分享，可在线阅读，更多相关《第八章排序(修订版本2010.6).doc（23页珍藏版）》请在金锄头文库上搜索。
1、第八章 排序内容提要：五类内部排序方法（插入排序、交换排序、选择排序、归并排序和基数排序）的基本思想、排序过程、实现的算法、算法的效率分析及排序的特点；各种排序方法的比较和选择；最后简单介绍外部排序。排序是数据处理中经常运用的一种重要运算。排序的功能是将一个数据元素(记录)的任意序列，重新排列成一个按关键字有序的序列。其目的之一是方便查找，从前一章可以看到，有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用查找效率较低的顺序查找法。又如建立树表的过程本身就是一个排序过程。因此，学习和研究各种排序方法有很大的意义。8.1 基本概念在学习排序之前，先学习几个基本术语。关键字是数据元
2、素中某个数据项的值，用它可以标识一个数据元素。通常会用记录来表示数据元素，一个记录可以由若干个数据项组成。例如：一个学生的信息就是一条记录，它包括学号、姓名、性别等若干数据项。见图8.1。图8.1 一记录结构主关键字是可以唯一地标识一个记录的关键字。如：学号。次关键字是可以标识若干记录的关键字。如：姓名、性别。假设一个文件有n条记录R1 ,R2 ,.,Rn，对应的关键字是K1 ,K2 ,.,Kn ，排序就是将此n个记录按关键字的大小递增(或递减)的次序排列起来，使这些记录由无序变为有序的一种操作。排序后的序列若为 Ri1 ,Ri2 ,.,Rin 时，其对应的关键字值满足Ki1Ki2,., Ki
3、n (或Ki1 Ki2，.,Kin)。若在待排序的记录中，存在两个或两个以上关键字相等的记录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的方法，否则是不稳定的方法。根据排序过程中涉及的存储器不同，可以将排序方法分为两大类：一类是内部排序，指的是待排序的记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是排序中要对外存储器进行访问的排序过程。内部排序是排序的基础，本章主要讨论内部排序，再介绍外部排序。在内部排序中，根据排序过程中所依据的原则可以将它们分为五类：插入排序、交换排序、选择排序、归并排序和基数排序；根据排序过程的时间复杂度来分，可分为三类：简单排序
4、、先进排序、基数排序。评价排序算法优劣标准主要是两条：一是算法的运算量，这主要是通过记录的比较次数和移动次数来反映；另一个是执行算法所需要的附加存储单元的多少。 为了讨论方便起见，假设待排序的一组记录存放在地址连续的一组存储单元上，并设记录的关键字均为整数，定义待排序的记录的数据类型为： typedef struct int key; elemtype data; redtype; redtype rn; key表示主关键字域；data表示其他域；redtype表示记录类型标识符。rn表示一个redtype类型的待排序数组。 8.2 插入排序插入排序的基本思想是：每步将一个待排序的记录，按其关
5、键字值的大小插入到前面已经排序的文件中适当的位置上，直到全部插入完为止。8.2.1 直接插入排序直接插入排序是一种简单的插入排序法，其基本思路是：把待排序的记录按其关键字的大小逐个插入到一个已经排好序的有序序列中去，直到所有的记录插入完为止，得到一个新的有序序列。例如，已知待排序的一组记录是： 60，71，49，11，82，24，3，66 假设在排序过程中，前3个记录已按关键字递增的次序重新排列，构成一个有序序列 49，60，71 现在将待排序记录中中的第4个记录(即11)插入上述有序序列，以得到一个新的含4个记录的有序序列。首先，应找到11的插入位置，再进行插入。可以将11放入数组的第一个单
6、元r0中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又再将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r0的值比较，11r0，它的插入位置就是r1。假设11大于第一个值r1，它的插入位置应在r1和r2之间，由于60已右移了，腾出来的位置正好留给11。后面的记录依照同样的方法逐个插入到该有序序列中。若记录数n，须进行n-1趟排序，才能完成。下面用图8.2说明整个排序过程。 在图8.2中，i表示插入记录的顺序号，用方括号括起来的部分表示已排序的记录。 i=1 60 71 49 11 82 49 3 66 i=2 71 6
7、0 71 49 11 82 49 3 66 i=3 49 49 60 71 11 82 49 3 66i=4 11 11 49 60 71 82 49 3 66i=5 82 11 49 60 71 82 49 3 66i=6 49 11 49 49 60 71 82 3 66i=7 3 3 11 49 49 60 71 82 66 i=8 66 3 11 49 49 60 66 71 82 监视哨r0图8.2 直接插入排序示例在排序之前设置了r0，r0称为“监视哨”，它的作用是免去在查找过程的每一步都要检测数组r是否查找结束、下标是否越界，这就是监视哨这个名称的来历。 图8.2中，序列60，7
8、1 称为第一趟排序。可见整个排序过程是由若干趟排序构成的。若记录数为n，直接插入排序应由双重循环来实现，外循环进行n-1趟插入排序，内循环用于进行一趟插入排序，即进行关键字的比较和记录的后移，完成某一记录的插入过程。直接插入排序的具体算法如下。 算法思路： （1）设置监视哨 r0，将待插入记录的值赋给r0; （2）设置开始查找的位置j；（3）在数组中进行搜索，搜索中将第j个记录后移，直至r0.keyrj.key为止 （4）将r0插入在rj+1的位置上算法8.1：void zjinsert(redtype r,int n)int i,j;for (i=2;i=n;i+) / r0=ri; /r0
9、j=i-1; /j-1while(r0.keyri.key) /rj+1=rj; /jr0.keyrj.keyj-;rj+1=r0; /r0 分析上述算法，为了正确地插入第i个记录，最多比较i次，最少比较1次，平均比较i/2次。按平均比较次数计算，将n个记录进行直接插入排序所需的平均比较次数为插入排序中记录的移动次数也是比较多的，用与上面类似的方法可以算出，插入n个记录所需的平均移动次数近似为n2/4。由此，直接插入排序的时间复杂度为O(n2)。由于直接插入排序在整个排序过程中只需一个记录单元的辅助空间，所以其空间复杂度为O（1）。直接插入排序是一种稳定的排序方法。 822 希尔排序希尔排序又称为“缩小增量排序”，也是一种插入排序类的算法，但在时间效率上有较大的改进。 希尔排序的思路是：选定第一个增量d1n，把全部记录按此值从第一个记录起进行分组，所有相距为d1的记录作为一组。先在各组内进行插入排序；然后减小间隔，取第二个增量d2=1) /以各种不同的间隔距离d进行排序for(i=d+1;i0)&(x.keyr2.key），则交换两个记录；然后比较第二个记录和第三个记录的关键字，若为逆序，又交换两个记录；如此下去，直至第n个记录和第n-1个记录的关键字进行比较完为止，这样就完
