资源预览内容
第1页 / 共89页
第2页 / 共89页
第3页 / 共89页
第4页 / 共89页
第5页 / 共89页
第6页 / 共89页
第7页 / 共89页
第8页 / 共89页
第9页 / 共89页
第10页 / 共89页
亲,该文档总共89页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第九章 排序内容提要: u五类内部排序方法(插入排序、交换排序 、选择排序、归并排序和基数排序)的基本 思想、排序过程、实现的算法、算法的效率 分析及排序的特点; u各种排序方法的比较和选择; u最后简单介绍外部排序。1排序的功能是将一个数据元素(记录)的任 意序列,重新排列成一个按关键字有序的 序列,目的是为了便于查询和处理数据。 排序的定义2排序的分类l按待排序记录所在位置 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问 的排序l按排序依据原则 插入排序:直接插入排序、折半插入排序 、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、堆排序 归并排序:2-路归并排序3排序的基本操作l比较两个关键字大小l将记录从一个位置移动到另一个位置4排序的性质如果在待排序的数据中,存在多个 关键字相同的数据,经排序后这些数 据的相对次序仍然保持不变,则称相 应的排序方法为稳定方法,否则为不 稳定方法。5定义待排序的记录的数据类型为:#define recnum 100 struct rectype int key; int item; ;struct rectype arecnum+1;排序对象的数据类型6基本思想:每步将一个待排序的记录,按其 关键字值的大小插入到前面已经排序的文件 中适当的位置上,直到全部插完为止。插入排序7基本思路是依次把待排序的记录逐一按其关 键字的大小插入到一个已经排好序的有序序 列中去,直到所有的记录插完为止。得到一 个新的有序序列。插入排序直接插入排序8例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827(13 27 38 49 65 76 97)排序结果:比较次数 移动次数1 11 02 1.1 05 56 5插入排序直接插入排序9(1)设置监视哨 a0,将待插入记录的 值赋给a0; (2)设置开始查找的位置j; (3)在数组中进行搜索,搜索中将第j个 记录后移,直至a0.keyaj.key为止 (4)将a0插入在aj+1的位置上直接插入排序算法10void straipass(a, i) struct rectype arecnum+1; int i; int j, x;a0=ai;j=i-1;x=ai.key;11while(x=j+1;k-)ak+1=ak; Aj+1=a0; 19void binsort(a,j)struct rectype arecnum+1;int j; int i;for(i=2;i=0 iaj+1.key)temp=aj;aj=aj+1;aj+1=temp; 34改进算法mark=i; while(mark) m=mark-1;mark=0;for(j=1;jaj+1.key)temp=aj; aj=aj+1; aj+1=temp;mark=j; 35由上述算法可见,当初始序列中记录已 按关键字次序排好序,则只需要进行一 趟排序,在排序过程中只需要进行n-1 次比较,记录移动次数为0;反之,若 初始序列中记录按逆序排列,若待排序 的序列有n个记录,最多进行n-1趟排序 ,最大比较次数为冒泡排序算法分析36冒泡排序交换记录时移动记录的次 数也约为3n2 /2次,故总的时间复杂 度为O(n2 )。冒泡排序是稳定的。37交换排序快速排序基本思想:通过一趟排序,将待排序记录分割成 独立的两部分,其中一部分记录的关键字均比另 一部分记录的关键字小,则可分别对这两部分记 录进行排序,以达到整个序列有序38对rst中记录进行一趟快速排序,附设两 个指针i和j,设枢轴记录rp=rs,x=rp.key u初始时令i=s,j=t u首先从j所指位置向前搜索第一个关键 字小于x的记录,并和rp交换 u再从i所指位置起向后搜索,找到第一 个关键字大于x的记录,和rp交换 u重复上述两步,直至i=j为止 u再分别对两个子序列进行快速排序, 直到每个子序列只含有一个记录为止快速排序的排序过程39例初始关键字: 49 38 65 97 76 13 27 50 ijxji完成一趟排序: ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序: ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束: 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij快速排序的排序过程401)确定第一个记录为基准记录rt,先从j所指示的位 置起向前扫描,当rt.keyrj.key时,交换rt.key 和rj.key,使关键字值比基准记录的关键字值小的 记录交换到前面; 2)从i所指示的位置起向后扫描,直到rt.keyri.key, 交换rt.key和ri.key,使关键字值比基准记录的关 键字值大的记录交换到后面; 3)重复(1)和(2),直至i=j为止完成一趟排序; 4)只要tw,重复(1)至(3)分别对基准记录两边 的部分进行排序。快速排序的排序算法41快速排序平均时间复杂度为O(nlog2 n)。最坏情况下时间复杂度为O(n2),快速排序所 需的比较次数反而最多。快速排序法不稳定。快速排序需要一个栈空间来实现递归。栈的 最大深度为 log2 n 1,所需栈空间为 O(log2 n)。最坏情况下,递归深度为n,所需 栈空间为O(n)。快速排序的排序算法分析42选择排序选择排序是指每次从待排序的记录中 选出关键字值最小(或最大)的记录,顺 序放在已排序的有序序列中,直到全部排 完。选择排序主要包括简单选择排序和堆 排序两种。43选择排序简单选择排序u首先通过n-1次关键字比较,从 n个记录中找出关键字最小的记录 ,将它与第一个记录交换 u再通过n-2次比较,从剩余的n- 1个记录中找出关键字次小的记录 ,将它与第二个记录交换 u重复上述操作,共进行n-1趟排 序后,排序结束44例初始: 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟: 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟: 13 27 65 97 76 49 38 三趟: 13 27 38 97 76 49 65 四趟: 13 27 38 49 76 97 65 五趟: 13 27 38 49 65 97 76 六趟: 13 27 38 49 65 76 97 排序结束: 13 27 38 49 65 76 97 45(1)查找待排序序列中最小的记录,并将它 和该区间第一个记录交换;(2)重复(1)到第n-1次排序后结束简单选择排序算法46简单选择排序所需要的总的比较次 数为O(n2 )。当初始文件是有序时,最 小移动记录次数等于0,而当初始文件 是逆序时,每次都要交换记录 。直接选择排序是不稳定的.简单选择排序算法分析47选择排序堆排序的引入堆排序是简单选择排序的改进。用直接 选择排序从n个记录中选出关键字值最小的 记录要做n-1次比较,然后从其余n-1个记录 中选出最小者要作n-2次比较。显然,相邻 两趟中某些比较是重复的。为了避免重复比 较,可以采用树形选择排序比较。 48(a)求出最小关键字3 (b) 求出次小关键字11 图 8.8 树形选择排序49树形选择排序总的比较次数为O(nlog2 n) ,与直接选择排序比较,减少了比较次数 ,但需要增加额外的存储空间存放中间比 较结果和排序结果。选择排序堆排序的引入50n个元素的序列(k1,k2,kn),当且仅当满足 下列关系时,称之为堆或(i=1,2,.n/2)kik2i kik2i+1kik2i kik2i+1例 (96,83,27,38,11,9)例 (13,38,27,50,76,65,49,97)962791138831327384965765097可将堆序列看成完全二叉树,则堆顶 元素(完全二叉树的根)必为序列中 n个元素的最小值或最大值堆的定义51堆排序的基本思路:对一组待排序的记 录序列,先将其关键字按堆的定义排列个 序列(称初建堆),找到了最小(最大)关 键字,将其取出。用剩余的n-1个元素再重建 堆,便可得到次小(次大)值。如此反复执 行,直到全部关键字排好序为止。 堆排序的基本思路52例13273849657650979727384965765013输出:132749389765765013输出:139749382765765013输出:13 273849502765769713输出:13 276549502738769713输出:13 27 38534965502738769713输出:13 27 387665502738499713输出:13 27 38 495065762738499713输出:13 27 38 499765762738495013输出:13 27 38 49 506597762738495013输出:13 27 38 49 509765762738495013输出:13 27 38 49 50 65547665972738495013输出:13 27 38 49 50 659765762738495013输出:13 27 38 49 50 65 769765762738495013输出:13 27 38 49 50 65 76 9755堆排序的关键问题堆排序需解决的两个问题: u如何由一个无序序列建成一个堆 ? u如何在输出堆顶元素之后,调整 剩余元素,使之成为一个新的堆 ?56堆排序的关键问题l第二个问题解决方法筛选 方法:输出堆顶元素之后,以堆中最后一个元素 替代之;然后将根结点值与左、右子树的根结点 值进行比较,并与其中小者进行交换;重复上述 操作,直至叶子结点,将得到新的堆,称这个从 堆顶至叶子的调整过程为“筛选”。l第一个问题解决方法建堆 方法:从无序序列的第n/2个元素(即此无序序 列对应的完全二叉树的最后一个非终端结点)起 ,至第一个元素止,进行反复筛选。57例:含8个元素的无序序列(49,38,65,97,76,13 ,27,50),建堆过程:49653827137697504965382713765097491338276576509749133827657650971327384965765097 58堆排序只需要一个记录大小的辅助空间。 堆排序算法的时间复杂度为O(nlogn)。 堆排序是一种不稳定的排序方法。堆排序的算法及分析59归并排序归并排序:把两个或多个有序表进行合 并,得到一个
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号