数据结构 第10章_内排序讲解

《数据结构 第10章_内排序讲解》由会员分享，可在线阅读，更多相关《数据结构 第10章_内排序讲解（130页珍藏版）》请在金锄头文库上搜索。

1、数据结构数据结构 李云清李云清 杨庆红杨庆红 揭安全揭安全 人民邮电出版社人民邮电出版社 高等学校精品课程（省级）高等学校精品课程（省级） 国家十二五规划教材国家十二五规划教材 高等学校精品课程（省级）高等学校精品课程（省级） 国家十二五规划教材国家十二五规划教材 揭安全揭安全 jieanquan jieanquan 江西师范大学计算机信息工程学院江西师范大学计算机信息工程学院 第第1010章章 内排序内排序 交换排序 pp 冒泡排序 p 快速排序 p 直接选择排序 p 堆排序 第十章 内排序 插入排序 p 直接插入排序 p 二分插入排序 p 希尔排序 选择排序 归并排序 基数排序 排序是数据

2、处理过程中经常使用的一种重要的运 算，排序的方法有很多种，本章主要讨论内排序的各 种算法，并对每个排序算法的时间和空间复杂性以及 算法的稳定性等进行了讨论。 10.1 排序的基本概念 假设一个文件是由n个记录R1，R2，Rn组成 ，所谓排序就是以记录中某个(或几个)字段值不减( 或不增)的次序将这n个记录重新排列，称该字段为 排序码。能唯一标识一个记录的字段称为关键码， 关键码可以作为排序码，但排序码不一定要是关键 码。 按排序过程中使用到的存储介质来分，可以将排 序分成两大类:内排序和外排序。 内排序是指在排序过程中所有数据均放在内存中 处理，不需要使用外存的排序方法。而对于数据量很 大的文

3、件，在内存不足的情况下，则还需要使用外存 ，这种排序方法称为外排序。 排序码相同的记录，若经过排序后，这些记录 仍保持原来的相对次序不变，称这个排序算法是稳 定的。否则，称为不稳定的排序算法。 评价排序算法优劣的标准 ： 首先考虑算法执行所需的时间，这主要是用执行 过程中的比较次数和移动次数来度量； 其次考虑算法执行所需要的附加空间。 当然，保证算法的正确性是不言而喻的，可读性 等也是要考虑的因素。 /*/ /*常见排序算法的头文件，文件名table.h */ /*/ #define MAXSIZE 100 /*文件中记录个数的最大值*/ typedef int keytype;/*定义排序码

4、类型为整数类型*/ typedef struct keytype key; int other;/*此处还可以定义记录中除排序码外 的其他域*/ recordtype;/*记录类型的定义*/ typedef struct recordtype rMAXSIZE+1; int length;/*待排序文件中记录的个数*/ table;/*待排序文件类型*/ void init(table *L) /*顺序表初始化函数*/ int i; srand(time(NULL); L-length=10; for (i=1;iri.key= rand(i)%100; void print(table L)

5、 /*顺序表输出函数*/ int i,k=0; for (i=1;ilength); for (i=1;ilength;i+) fscanf(fp,“%d“, else L-length=0; 10 50 30 20 90 10 70 80 40 60 100 一个输入文件的例子 10.2 插入排序 插入排序的基本方法是: 将待排序文件中的记录， 逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置，并保持新文件有序。 10.2.1 直接插入排序 直接插入排序算法的思路是:初始可认为文件中的 第1个记录己排好序，然后将第2个到第n个记录依次 插入已排序的记录组成的

6、文件中。在对第i个记录Ri进 行插入时，R1，R2，Ri-1已排序，将记录Ri的排序 码keyi与已经排好序的排序码从右向左依次比较，找 到Ri应插入的位置，将该位置以后直到Ri-1各记录顺序 后移，空出该位置让Ri插入。 直接插入排序演示 0 1 2 3 4 5 6 21 25 4949 25* 16 08 i =3 21 25 49 25* 16 08 0 1 2 3 4 5 6 初态 49 0 1 2 3 4 5 6 2121 2525* 16 08 i = 2 49 25 0 1 2 3 4 5 6 i = 6 i = 5 21 25 0808 0 1 2 3 4 5 6 21 49

7、25* 16 08 0 1 2 3 4 5 6 49 25* 1616 21 25 49 25* 16 0808 i = 4 25* 16 08 25 21 49 25* 16 08完成 25 习题：给出初始数列47，28，32，15，94，33 ，14，16在直接插入排序下的状态变化过程。 472832 15 9433 1416初态： i=2 i=3 i=4 i=5 i=6 i=7 284732 15 9433 1416 283247 15 9433 1416 152832 47 9433 1416 152832 47 9433 1416 152832 33 4794 1416 141528

8、 32 3347 9716 141516 28 3233 4797i=8 void insertsort(table *L) /*直接插入排序*/ int i,j; for (i=2;ilength;i+) j=i-1; L-r0=L-ri; /*放置哨兵*/ while ( L-rj.keyL-r0.key ) L-rj+1=L-rj; j-; L-rj+1=L-r0; 算法10.1 直接插入排序算法 直接插入排序算法执行时间的分析： 最好的情况 ： 即初始排序码开始就是有序的情况下，直接插入 排序算法的比较次数为(n-1)次，移动次数为2*(n-1) 次。 最坏情况 ： 即初始排序码开始是

9、逆序的情况下，因为当插入 第i个排序码时，该算法内循环while要执行i次条件判 断，循环体要执行i-l次，每次要移动1个记录，外循 环共执行n-1次，其循环体内不含内循环每次循环要 进行2次移动操作，所以在最坏情况下，比较次数为 (1+2+n)。 直接插入排序算法的时间复杂度为O(n2)。 10.2.2 二分法插入排序 二分法插入排序的思想： 根据插入排序的基本思想，在找第i个记录的插 入位置时，前i-l个记录已排序，将第i个记录的排序码 keyi和已排序的前i-1个的中间位置记录的排序码进 行比较，如果keyi小于中间位置记录排序码，则可以 在前半部继续使用二分法查找，否则在后半部继续使

10、用二分法查找，直到查找范围为空，即可确定keyi的 插入位置。 void binarysort(table *L) /*折半插入排序*/ int left,right,mid,i,j; for(i=2;ilength;i+) L-r0=L-ri; /*保存待插入的元素*/ left=1; right=i-1; /*设置查找范围的左、右 位置值*/ while (leftri.keyrmid.key) right=mid-1; else left=mid+1; /*插入位置为left*/ for(j=i-1;j=left;j-) /*后移留空*/ L-rj+1=L-rj; L-r left =L

11、-r0; /*插入第i个元素的副本*/ 算法10.2 二分法插入排序算法 二分法插入排序算法，在查找第i个记录的插入 位置时，每执行一次while循环体，查找范围缩小一 半，和直接插入排序的比较次数对比，二分法插入的 比较次数少于直接插入排序的最多比较次数，而一般 要多于直接插入排序的最少比较次数。总体上讲，当 n较大时，二分法插入排序的比较次数远少于直接插 入排序的平均比较次数，但二者所要进行的移动次数 相等，故二分法插入排序的时间复杂度也是O(n2)，所 需的附加存储空间为一个记录空间。 10.2.3 表插入排序 二分法插入排序比较次数通常比直接插入排序 的比较次数少，但移动次数相等。表插

12、入排序将在不 进行记录移动的情况下，利用存储结构有关信息的改 变来达到排序的目的。 给每个记录附设一个所谓的指针域link，它的类 型为整型，表插入排序的思路：在插入第i个记录Ri时 ，R1，R2，Ri-1已经通过各自的指针域link按排序 码不减的次序连接成一个（静态链）表，将记录Ri的 排序码keyi与表中已经排好序的排序码从表头向右、 或称向后依次比较，找到Ri应插入的位置，将其插入 在表中，使表中各记录的排序码仍然有序。 /* 表插入排序定义的头文件，文件名为：table2.h */ #define MAXSIZE 100 /*文件中记录个数的最大值*/ typedef int key

13、type; /*定义排序码类型为整数类型*/ typedef struct keytype key; int link; recordtype; /*记录类型的定义*/ typedef struct recordtype rMAXSIZE+1; int length; /*待排序文件中记录的个数*/ table2; /*待排序文件类型*/ 表插入排序算法的示意如图10.4所示 key link 31212627222628165123 下标 0 1 2 3 4 5 6 7 （a）初始存储状态 下标 0 1 2 3 4 5 6 7 （b）由第1个记录构成的有序表 下标 0 1 2 3 4 5 6

14、 7 （c）插入第2个记录构成的有序表 key link 31212627222628165123 1 0 key link 31212627222628165123 2 0 1 表插入排序算法：初始时，r0.Link用于存放表 中第1个记录的下标，r0.Link的值为1，排序结束时 ，r0.Link中存放的是所有排序码中值最小的对应记 录的下标，其它的排序码通过各自的指针域link按不减 的次序连接成一个（静态链）表，最大的排序码对应 的link为0。 key link 31212627222628165123 5 0 6 1 3 7 4 2 下标 0 1 2 3 4 5 6 7 （d）所有记录都插入后的结束状态（下标为5的记录的key值最小） 图10.4 表插入排序算法示意图 void tableinsertsort(table2 *tab) int i,p,q; tab-r0.link=1; tab-r1.link=0; /*第1个元素为有序静态表*/ for(i=2;ilength;i+) /*依次插入从第2个开始的所有 元素*/ q=0;p=tab-r0.link; /*p指向表中第1个元素，q指向 p的前驱元素位置*/ while(p!=0 p=tab-rp.link; /*继续查找*/