《第九章排序》由会员分享，可在线阅读，更多相关《第九章排序（195页珍藏版）》请在金锄头文库上搜索。
1、数据结构 9排序主要内容 什么是排序 内部排序 插入式排序：直接插入排序法、希尔排序法 交换式排序：起泡法、快速排序法 选择式排序：直接选择排序法、树形选择排序法、堆排序 归并排序 基数排序 各种内部排序方法的比较 将n个性质相同的数据元素（通常都是杂乱无章的）按待排关键字值从小到大或从大到小（规律）排为有序序列的操作称作排序。 排序的目的：便于查找。注意当按次关键字进行排序时，由于可能存在关键字值相同的元素，因而排序结果不唯一。9.1 什么是排序 按排序的规则(“扩大”有序序列长度的方法)不同，内部排序的算法可分为5类： 插入排序、交换排序、选择排序、归并排序、基数排序关键字的位数(长度)按
2、排序算法的时间复杂度不同，可分为3类：v简单排序算法：时间效率低，O(n2)v先进排序算法: 时间效率高，O(nlog2n)v基数排序算法：时间效率高，O(dn)排序的分类 按文件的存储结构分： a.连续顺序文件排序 排序时直接移动记录 b.链表排序 排序时只移动指针排序的分类 按排序的稳定性分： 稳定性排序 不稳定性排序 对于值相同的两个元素，排序前后的先后次序不变，则称该排序方法为稳定的，否则为不稳定的。排序的分类举例原序列排序结果学号姓名成绩1王云672李永强833刘小玲724赵祥925陈晓壮83学号姓名成绩1王云673刘小玲722李永强835陈晓壮834赵祥92排序方法A必然稳定的排序
3、方法原序列排序结果学号姓名成绩1王云672李永强833刘小玲724赵祥925陈晓壮83学号姓名成绩1王云673刘小玲725陈晓壮832李永强834赵祥92排序方法B可能非稳定的排序方法举例 排序算法优劣的衡量 时间复杂度（分析记录关键字的比较次数和记录的移动次数）l 平均情况l 最好情况和最差情况：有一些算法，其复杂度受最初数据的排列情况影响较大l 可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数什么是排序 排序算法优劣的衡量 空间复杂度l 排序时所需的额外的辅助存储空间l 额外：指除了存放数据元素占用的存储空间之外，执行算法所需要的其他存储空间l 理想的空间效率是
4、算法执行期间所需要的辅助空间与待排序的数据量无关什么是排序 教材采用的排序表的结构定义typedef struct int key; /数据元素的关键字 datatype other; /数据元素中的其它域rectype; /一条数据记录 rectype Rn; /记录型数组什么是排序F直接插入排序法F 折半插入排序法F 希尔排序法9.2 插入式排序 基本思想： 每一步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的文件中的适当位置上，直到全部记录插入为止 第i趟排序将序列的第i+1个元素ki+1插入到一个大小为i，且已按值有序的序列k1,k2,ki的合适位置，得到一个大小为i+1，
5、并且仍然保持按值有序的序列k1,k2,ki+19.2 插入式排序 类比：扑克牌抓牌22223344445533559.2 插入式排序设对数据元素序列R1,R2,Rn进行排序，则：(1)仅含R1的序列是长度为1的按关键字值有序的序列；4938659776132749temp01234567初始方法 举例直接插入排序（最简单的排序法！）(2)依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法493865977613274901234567一趟比较次数移动次数1次1次2次3次temp 举例直接插入排序（最简单的排序法！）384965977613
6、274901234567二趟比较次数移动次数1次temp(2)依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法 举例直接插入排序：基本思想384965977613274901234567三趟比较次数移动次数1次temp(2)依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法 举例直接插入排序：基本思想384965977613274901234567四趟比较次数移动次数1次1次2次3次2次temp(2)依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序
7、列仍按关键字值有序。方法 举例直接插入排序：基本思想384965769713274901234567五趟比较次数移动次数1次1次2次3次2次3次4次4次5次5次6次7次temp(2)依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法 举例直接插入排序：基本思想133849657697274901234567六趟比较次数移动次数1次1次2次3次2次3次4次4次5次5次6次6次temp(2)依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法 举例直接插入排序：基本思想7次13273849
8、6576974901234567七趟比较次数移动次数1次1次2次3次2次3次4次4次5次temp(2)依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例直接插入排序：基本思想 算法void INSERTSORT(rectype R) /*insertsort.c*/int i,j; for(i=2;i=n;i+) /依次插入R2,Rn R0 = Ri; /用R0先记录Ri的值 j=i-1; /j指示当前空位置的前一个元素 while(R0.key0) for (i=d+1;i0) if (rj.keyrj+d.key) r0=rj;
9、/*将rj与rj+d进行交换*/ rj=rj+d; rj+d=r0; j=j-d; else j=0; d=d/2; /*减小增量*/ 回顾直接插入排序的特点： 数据大致有序时最快，O(n) 希尔排序的原理 在希尔排序中，关键字较小的元素能跳跃式地前移，从而在进行最后一趟增量为1的插入排序时，序列已基本有序，只要进行少量的比较和移动即可完成排序，因而时间复杂度较直接插入排序低。 希尔排序的时间复杂度与所取增量序列有关。增量序列可有各种取法，但各增量值间应无除1之外的公因子，且最后一个增量值必为1。希尔排序(缩小增量排序) 时间复杂度： O(n(log2n)2) 空间复杂度： O(1) 稳定性：
10、 不稳定希尔排序(缩小增量排序)以关键字序列(256,301,751,129,937,863,742,694,076,438)为例，写出执行希尔排序（取d=5,3,1）算法的各趟排序结束时，关键字序列的状态。解：原始序列: 256,301,751,129,937,863,742,694,076,4381:d=5256,301,694,076,438,863,742,751,129,937076,301,129,256,438,694,742,751,863,937076,129,256,301,438,694,742,751,863,9372:d=33:d=1F 起泡排序法F 快速排序法9.3
11、 交换排序方法设对数据元素序列R1,R2,Rn进行排序，则：(1)对相邻的两个数据元素的关键字值进行比较，若为逆序，则交换；(2)一趟排序完成后，关键字值最大的数据元素排在了最后，如此重复n-1次，即可完成排序。起泡排序法举例497初始049138265397476513627一趟比较次数移动次数1次3次6次9次2次3次 12次4次 15次5次6次7次起泡排序法97初始38496576132749一趟比较次数移动次数1次3次6次9次2次3次4次5次6次二趟15次7次70123456起泡排序法举例三趟二趟97初始38496513274976一趟比较次数移动次数1次3次6次9次2次3次4次5次15
12、次7次9次6次70123456起泡排序法举例四趟二趟97初始38491327496576一趟比较次数移动次数1次3次6次2次3次4次15次7次9次6次三趟9次5次70123456起泡排序法举例五趟二趟97初始38132749496576一趟比较次数移动次数1次3次6次2次3次15次7次9次6次三趟9次5次比较次数移动次数四趟6次4次70123456起泡排序法举例六趟二趟97初始13273849496576一趟比较次数移动次数1次2次15次7次9次6次三趟9次5次比较次数移动次数四趟6次4次五趟6次3次70123456起泡排序法举例 void BubbleSort(rectype a, int
13、n) int i, j, flag = 1; rectype temp; for(i = 1; i n & flag = 1; i+) flag = 0; /每趟比较前设置flag=0，假定该序列已有序 for(j = 1; j aj+1.key) flag = 1; temp = aj; aj = aj+1; aj+1 = temp; if(!flag) break; 该算法中，外层循环控制排序的执行趟数，内层循环用于控制在一趟冒泡排序中相邻记录间的比较和交换。注意:1. 起泡排序的结束条件为，最后一趟没有进行“交换记录”。2. 一般情况下，每经过一趟”起泡”，参加扫描的元素个数要-1，但并
14、不是每趟都如此。起泡排序法5231978for(j = 1; j aj+1.key) j=1i=725 35 1579 89i=613i=2void BubbleSort(rectype a, int n) while (i1) / while / BubbleSorti=n;i=lastExchangeIndex; /本趟进行过交换的最后一个记录的位置 if(aj.key aj+1.key) Swap(aj, aj+1); lastExchangeIndex = j; /记下进行交换的记录位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1; 时间复
15、杂度 最好情况：所有数据已经排好了序u只需要扫描1趟，比较n-1次 最坏情况：初始排列逆序，算法要执行n-1趟起泡，第i趟(1=in)做了n-i次关键码比较，执行了n-i次对象交换。此时的比较总次数KCN和记录移动次数RMN为：起泡排序法 时间复杂度 最好：O(n) 最差：O(n2) 平均：O(n2) 空间复杂度 O(1)：交换时需要一个临时变量 稳定性：稳定 49和49*在排序前后的次序未改变起泡排序法方法设对数据元素序列Rs,Rt进行排序，则：(1)若s=t，即序列中仅一个元素，则排序完成；(2)若st，则以Rs为枢轴进行一趟快速排序：493865977613274901234567初始快
16、速排序4938659776132749一趟hlw 令low=s，high=t；w 从high所指位置开始向前找第一个关键字值小于枢轴关键字值的元素，若该元素在枢轴之后，则交换两者的位置；01234567快速排序4938659776132749一趟hl01234567w从low所指位置开始向后找第一个关键字值大于枢轴关键字值的元素，若该元素在枢轴之前，则交换两者的位置；快速排序4938659776132749一趟hlw 如此重复直至high=low，则本趟快排完成；01234567快速排序4938659776132749二趟hl(3)分别对枢轴元素之前和之后的序列进行快排。01234567快速排序4938659776132749二趟hl01234567(3)分别对枢轴元素之前和之后的序列进行快排。快速排序4938659776132749三趟hl01234567(3)分别对枢轴元素之前和之后的序列进行快排。快速排序 最理想的情况： 疑问 运气哪有这么好，总能“一刀切”？ 为了把一个元素放到正确的位置上，扫描了剩下的所有元素，复杂度仍然是O(n2)，“快速”在哪里？5 4 2 1 3 8 6
