《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第9章 排序》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第9章 排序（85页珍藏版）》请在金锄头文库上搜索。
1、9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较和选择 9.8 外排序简介,第9章 排 序,1、概述 排序是将一组无序的数据元素序列按一定规律进行排列，使其成为有序序列。排序是数据处理中的一种重要运算，如何进行排序，特别是高效率地进行排序是程序设计中所要研究的重要问题之一。 排序在日常生活中也是屡见不鲜的。例如，学生成绩的排名，人事管理部门对职工的排列、运动项目中运动员的排名等，这些均属于排序的例子，排序的目的是便于以后检索其成员，例如，电话号码簿、目录表、图书馆、字词典等一切需对所存对象进行检索的地方
2、，都要先将对象加以排序。,9.1 排序的基本概念,2、排序的定义 假设含有n条记录的序列为 R1，R2，Rn，其相应的关键字序列为 K1，K2，Kn，排序就是将此n条记录按照关键字值的大小递增或递减方式对这些记录进行排列，使这些记录由无序变为有序的一种操作，即排序后得到的序列若为Ri1，Ri2，Rin，则其对应的关键字值满足 Ki1Ki2，Kin或Ki1Ki2，Kin。 3、排序分类 （1）稳定排序与不稳定排序 如果在待排序的记录中，存在有多个关键字相同的记录（如Ri和Rj的关键字相同，即Ki =Kj），若在排序操作之前，Ri在Rj之前，若采用某种排序方法进行排序之后，这些具有相同关键字的记录
3、如Ri和Rj其相对次序保持不变即Ri仍在Rj之前，此时称这种排序方法为稳定排序；相反，若在排序后的序列中Ri与Rj的相对次序发生变化即Ri在Rj之后，此时称这种排序方法是不稳定的。,（2）内排序与外部排序 可根据记录所处的环境即按照排序过程中所使用的内、外存情况的不同，将排序分为内排序和外排序两大类别。若利用某一种排序方法在排序过程中全部数据都存放在内存中即排序时没有进行内、外存数据交换，则称这种排序方法为内排序；若排序过程中全部记录不能同时存放在内存，需要进行数据的内、外存交换，则称这种排序方法为外排序。显然，内排序适用于一些记录数目不很多的文件。对于一些较大的文件，由于内存容量的限制，不能
4、一次全部装入内存进行排序，也只得采用外排序来实现，但是外排序的速度要比内排序速度慢得多。 内排序方法很多，按照排序中所用策略的不同，它一般可分为五类：插入排序、选择排序、交换排序、归并排序和基数排序。每一类中不同的排序算法都是基于同一策略的不同方法。外部排序多是采用多路归并方法进行排序。,4、待排序文件的组织形式与算法评价 以一维数组作为组织形式，排序过程是对记录本身进行物理重排，通过比较和判定把记录移动到合适的位置； 以链表作为组织形式，排序过程中无需移动记录，仅需修改指针即可，通常把这类排序称为表排序； 为待排序文件组织一个辅助表，如组织一张含关键字和指向记录指针的索引表，在排序过程中只需
5、对辅助表的表目进行物理重排，不需移动记录本身，在排序结束后按辅助表调整记录位置。 为了讨论方便起见，假设在内排序中，待排序的n条记录通常被存放在一个一维数组中。 一般通过衡量整个排序过程在最坏或平均情形下进行的记录的比较和移动次数即通过排序的时间复杂性来衡量一个排序算法的好坏。有时还需要分析执行算法所需的附加存储空间和它稳定性和简单性等。,5、数据类型定义 本章如无特别说明，均假设待排序的一组记录存放在一组地址连续的存储单元之中，并设记录关键字均为整数，待排序记录的数据类型为： typedef struct /*记录为一结构型类型*/ int key; /*关键字域*/ elemtype ot
6、heritem； /*记录的其它域*/ recdtype; recdtype Rn ； /*R为一个记录类型数组*/,插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录序列的适当位置，直到全部记录插入完成为止。本节将介绍直接插入排序、希尔排序和其它如二分法插入排序、二路插入排序和共享栈插入排序等。 9.2.1 直接插入排序 1、具体做法 直接插入排序是一种最简单的排序方法。它的具体做法是：依次把待排序的记录逐一地按其关键字值的大小插入到一个已排好序的有序序列中，得到一个新的有序序列，直到所有的记录插入完毕为止，从而实现排序。,9.2 插入排序,例如，已知待排
7、序的一组记录对应的关键字为：13，38，22，97，76，65，38，58，而且记录中的前2个记录已按关键字值递增有序即13，38，现要将上面记录中的第三个记录（即关键字22所对应的记录）插入到上述的有序序列中，以得到一个新的含有3个记录的有序序列。 显然，首先需要检索到22的正确插入位置，再进行插入，从而得到一个新的有序序列，其对应的关键字序列为13，22，38，此时称作进行了一趟直接插入排序过程。整个直接插入排序的过程为：先将第一个记录作为一个有序序列，然后从第二个记录起逐个插入到该有序序列中去，使得插入后仍然是有序的，这样不断下去，直到排序结束。显然，若记录个数为n时，必须进行n-1趟插
8、入排序。,2、算法实现 void insertsorting（ recdtype R ）/*对R数组按递增方式进行插入排序*/ int i，j ; for ( i=2；i=n；i +) /*设全部记录存放在R1至Rn中*/ R0 =Ri； /*设监视哨R0*/ j = i-1； /*从j=i-1起往前搜索*/ while (R0.key Rj.key) /*确定插入位置*/ Rj+1 =Rj； /*将第j个记录赋值给第j+1个记录，即后移记录*/ j - -; Rj+1 = R0; /*找到位置后插入第i个记录*/ /*insertsorting */,3、直接插入排序示例 前面所给例子的直接
9、插入排序过程如图9.1所示。,4、性能分析 由排序过程及算法可知，其时间主要花费在关键字的比较和记录的后移操作上。当初始文件记录关键字的分布情况不同时，算法在执行过程中的花费时间是有差异的。对于一个含有n个记录的文件，若初始文件按关键字递增有序（即正序），此时n-1趟排序总的关键字比较次数为最小值 n-1次，并且排序过程总的记录移动次数也为最小值2(n-1)次；反之，若初始文件按关键字递减有序（即反序），此时关键字的比较次数和记录移动次数均取最大值，使得插入排序出现最坏情况。在最坏情况下关键字的比较总次数的最大值Cmax和记录移动总次数的最大值Mmax 为： Cmax = =(n+2)(n-1
10、)/2 Mmax = =(n-1)(n+4)/2,在最好情况下即初始文件是正序时，此时算法的时间复杂度为O（n）；在最坏情况下即初始文件是反序时，此时算法的时间复杂度为O（n2）。若初始文件记录的排列情况为随机排列，其时间复杂度为O（n2）。 直接插入排序在整个排序过程中只需一个记录单元的辅助空间（即R0），所以其空间复杂度为O（1），且直接插入排序是一种稳定的排序方法。,9.2.2 希尔排序 希尔排序又称为缩小增量排序（Diminishing Increatment Sort），它是1959年由希尔（D.L.Shell）提出来的对直接插入排序的一种改进的排序方法。 由直接插入排序的分析可知，
11、在初始文件为反序时其时间复杂度为O（n2）。若初始文件已按关键字基本有序，则文件中的大多数记录都不需要进行插入，整个排序所花费的时间可大大减少，此时，其效率可大大地提高；另一方面，当文件所含的记录数目n很小时，n2值受n的值的影响不很大，即在n较小时，直接插入排序的效率也比较高，希尔排序正是由此出发而获得的一种改进的插入排序方法。 希尔排序的基本做法是：先选取一个小于n的整数d1作为第一个增量，把文件的所有记录分成d1个组，所有距离为d1倍数的记录都放在同一个组内，在各组内进行直接插入排序；然后，取第二个增量d2d1，重复上述分组和排序过程，直到所取的增量di = 1，(di di-1 d2
12、d1)，此时所有记录放在同一组内进行直接插入排序。,例如，对于一个具有8个记录的文件进行希尔排序的过程可由图9.2进行说明，各趟增量序列可取4、2、1。 第一趟排序时，d1 = 4，此时整个文件被分成4组，即(R1，R5)，(R2，R6)，(R3，R7)，(R4，R8)，每一组中的第一个记录都自成一个有序区，可依次将各组的第二个记录R5，R6，R7，R8分别插入到各组中的有序区中，使文件各组均有序，得到第一趟排序结果。 第二趟排序时，可取增量d2 =2，此时把整个文件分成二组(R1，R3，R5，R7)和(R2，R4，R6，R8)，各组内的第一个记录仍自成一个有序区，然后同样可在各组内进行直接插
13、入排序，使各组内记录有序，得到第二趟排序结果。 第三趟排序时，可取增量d3 =1，此时整个文件为一组，对整个文件进行直接插入排序，得到第三趟排序结果；从而达到整个文件按关键字有序，即实现排序。,下面分别给出不设监视哨和设置监视哨的两个希尔排序算法。 （1）若不设置监视哨，希尔排序的算法可描述如下： void shellsorting（recdtype R ，int n） /*希尔排序算法*/ recdtype x; int d，bool，i，j ； d=n ； while (d =1) /*dRj.key),x=Ri； Ri = Rj; Rj=x； bool=0; while (!bool)
14、/*shellsort*/,（2）若利用监视哨希尔排序的算法 recdtype Rn+d1 ; /*R0 到 Rd1-1为d1个监视哨*/ int dm ; /*设d0到dm-1存放增量序列*/ void shellsort ( R，d) recdtype R ； int d ; int i， j，k，t； recdtype temp； int maxint=32767; /*设为最大机器整数*/ for (i= 0；id0；i+) Ri.key=-maxint; /*设置监视哨 */ k =0; /*取第一个增量单元的下标*/ do t= dk; /*取本趟增量*/ for (i = t+d
15、1；in+d1；i+) temp = Ri ; /保存待插入记录Ri*/ j = i-t； while (temp.key Rj.key /*查找正确的插入位置*/,Rj+t = Rj; /*后移记录*/ j = j-t; /*查找前一个记录的插入位置*/ Rj+t = temp; /*插入Ri*/ /*结束本趟查找*/ k +; /*取下一个增量*/ while (t! =1) /*增量为1，排序终止*/ /*shellsort*/,希尔排序方法的一开始组数较多而组中记录较少，各组中记录的直接插入排序是处在n值很小的情况下进行，有着较高的效率；并且在不满足次序时的移动，是用较少的移动次数而得
16、到了记录的较大移动距离。随着di减小，组数变少组中记录个数变多的同时，组中记录也逐步变得基本有序，使得在一趟中进行直接插入排序时的效率大大地提高，从而提高了排序速度。在希尔排序中，每一趟的增量di的取值对排序效果会产生较大的影响。对于每一趟的增量di可有不同的取法。如何选择增量序列才能产生最好的排序效果，至今仍无法从数学上得到圆满解决，但是最后的那一个增量值必须等于1，以实现整个文件的有序。 前面给出的两个希尔排序算法，shellsorting和shellsort的时间复杂度为O(n(log2n)2)。希尔排序是不稳定的排序算法。,1、折半插入排序 把直接插入排序中检索插入位置的方法（由后向前顺序检索）改为折半检索
