第八部分排序技术.ppt
《第八部分排序技术.ppt》由会员分享,可在线阅读,更多相关《第八部分排序技术.ppt(112页珍藏版)》请在三一文库上搜索。
1、第八章 排序技术,本章的基本内容是: 排序的基本概念 插入排序 交换排序 选择排序 归并排序,概 述,排序:给定一组记录的集合r1, r2, , rn,其相应的关键码分别为k1, k2, , kn,排序是将这些记录排列成顺序为rs1, rs2, , rsn的一个序列,使得相应的关键码满足ks1ks2ksn(称为升序)或ks1ks2ksn(称为降序)。 正序:待排序序列中的记录已按关键码排好序。 逆序(反序):待排序序列中记录的排列顺序与排好序的顺序正好相反。,排序的基本概念,排序算法的稳定性:假定在待排序的记录集中,存在多个具有相同键值的记录,若经过排序,这些记录的相对次序仍然保持不变,即在原
2、序列中,ki=kj且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。,概 述,排序的基本概念,概 述,排序的基本概念,单键排序:根据一个关键码进行的排序; 多键排序:根据多个关键码进行的排序。,按学号排序单键排序 按成绩(高数英语思想品德)排序多键排序,概 述,排序的基本概念,设关键码分别为k1, k2, , km,多键排序有两种方法: 依次对记录进行m次排序,第一次按k1排序,第二次按k2排序,依此类推。这种方法要求各趟排序所用的算法是稳定的; 将关键码k1, k2, , km分别视为字符串依次首尾连接在一起,形成一个新的字符串,然后,对记录
3、序列按新形成的字符串排序。,排序的分类 1. 内排序:在排序的整个过程中,待排序的所有记录全部被放置在内存中 2. 外排序:由于待排序的记录个数太多,不能同时放置在内存,而需要将一部分记录放置在内存,另一部分记录放置在外存上,整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。,概 述,排序的基本概念,排序的分类 1. 基于比较:基本操作关键码的比较和记录的移动,其最差时间下限已经被证明为(nlog2n)。 2. 不基于比较:根据关键码的分布特征。,概 述,排序的基本概念,基于比较的内排序 1. 插入排序 2. 交换排序 3. 选择排序 4. 归并排序,1. 基本操作。内排序在排序过程
4、中的基本操作: 比较:关键码之间的比较; 移动:记录从一个位置移动到另一个位置。 2. 辅助存储空间。 辅助存储空间是指在数据规模一定的条件下,除了存放待排序记录占用的存储空间之外,执行算法所需要的其他存储空间。 3.算法本身的复杂程度。,排序算法的性能,概 述,排序算法的存储结构,概 述,从操作角度看,排序是线性结构的一种操作,待排序记录可以用顺序存储结构或链接存储结构存储。,假定2:将待排序的记录序列排序为升序序列。,int rn+1; /待排序记录存储在r1rn,r0留做他用,假定1:采用顺序存储结构,关键码为整型,且记录只有关键码一个数据项。,插入排序,插入排序的主要操作是插入,其基本
5、思想是:每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中,直到全部记录排好序为止。,基本思想:在插入第 i(i1)个记录时,前面的 i-1个记录已经排好序。,直接插入排序,插入排序,基本思想:在插入第 i(i1)个记录时,前面的 i-1个记录已经排好序。,(1)如何构造初始的有序序列? (2)如何查找待插入记录的插入位置?,直接插入排序,插入排序,需解决的关键问题?,直接插入排序过程示例,r 0 1 2 3 4 5 6,21,18,25,22,10,25*,21,插入排序,22,10,25,18,18,r0的作用?,暂存单元,监视哨,解决方法: 将第1个记录看成是初始有序
6、表,然后从第2个记录起依次插入到这个有序表中,直到将第n个记录插入。,插入排序,关键问题(1)如何构造初始的有序序列?,算法描述: for (i=2; i=n; i+) 插入第i个记录,即第i趟直接插入排序; ,关键问题(2)如何查找待插入记录的插入位置?,解决方法: 在i-1个记录的有序区r1 ri-1中插入记录ri,首先顺序查找ri的正确插入位置,然后将ri插入到相应位置。,r0有两个作用: 1. 进入循环之前暂存了ri的值,使得不致于因记录的后移而丢失ri的内容; 2. 在查找插入位置的循环中充当哨兵。,插入排序,算法描述: r0=ri; j=i-1; while (r0rj) rj+1
7、=rj; j-; ,void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0rj) rj+1=rj; j=j-1; rj+1=r0; ,直接插入排序算法,插入排序,直接插入排序算法性能分析,最好情况下(正序):,插入排序,时间复杂度为O(n)。,直接插入排序算法性能分析,插入排序,最好情况下(正序):,最坏情况下(逆序或反序):,时间复杂度为O(n2)。,时间复杂度为O(n)。,平均情况下(随机排列):,直接插入排序算法性能分析,插入排序,时间复杂度为O(n2)。,空间性能:需要一个记录的辅助空间。 直
8、接插入排序算法是一种稳定的排序算法。,直接插入排序算法性能分析,插入排序,直接插入排序算法简单、容易实现,适用于待排序记录基本有序或待排序记录较小时。 当待排序的记录个数较多时,大量的比较和移动操作使直接插入排序算法的效率降低。,插入排序,如何改进直接插入排序?,注意到,在插入第 i(i1)个记录时,前面的 i-1 个记录已经排好序,则在寻找插入位置时,可以用折半查找来代替顺序查找,从而较少比较次数。,请同学们写出这个改进的直接插入排序算法,并分析时间性能。,希尔排序,改进的着眼点: (1)若待排序记录按关键码基本有序时,直接插入排序的效率可以大大提高; (2)由于直接插入排序算法简单,则在待
9、排序记录数量n较小时效率也很高。,插入排序,(1)应如何分割待排序记录,才能保证整个序列逐步向基本有序发展? (2)子序列内如何进行直接插入排序?,插入排序,需解决的关键问题?,基本思想:将整个待排序记录分割成若干个子序列,在子序列内分别进行直接插入排序,待整个序列中的记录基本有序时,对全体记录进行直接插入排序。,希尔排序,基本有序:接近正序,例如1, 2, 8, 4, 5, 6, 7, 3, 9; 局部有序:部分有序,例如6, 7, 8, 9, 1, 2, 3, 4, 5。 局部有序不能提高直接插入排序算法的时间性能。,插入排序,希尔排序,分割待排序记录的目的?,1. 减少待排序记录个数;
10、2. 使整个序列向基本有序发展。,子序列的构成不能是简单地“逐段分割”,而是将相距某个“增量”的记录组成一个子序列。,启示?,希尔插入排序过程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,插入排序,30,08,13,解决方法: 将相隔某个“增量”的记录组成一个子序列。 增量应如何取? 希尔最早提出的方法是d1=n/2,di+1=di/2。,关键问题(1)应如何分割待排序记录?,插入排序,算法描述: for (d=n/2; d=1; d=d/2) 以d为增量,进行组内直接插入排序; ,解决方法: 在插入记录ri时,自ri-d起往前跳跃式(跳跃幅度为d)
11、搜索待插入位置,并且r0只是暂存单元,不是哨兵。当搜索位置0,表示插入位置已找到。 在搜索过程中,记录后移也是跳跃d个位置。 在整个序列中,前d个记录分别是d个子序列中的第一个记录,所以从第d+1个记录开始进行插入。,插入排序,关键问题(2)子序列内如何进行直接插入排序?,算法描述:,for (i=d+1; i0 ,插入排序,关键问题(2)子序列内如何进行直接插入排序?,希尔排序算法的时间性能,希尔排序算法的时间性能是所取增量的函数,而到目前为止尚未有人求得一种最好的增量序列。 研究表明,希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内,希尔排序所需的比较次数和记录
12、的移动次数约为O(n1.3 ) 。,插入排序,希尔排序开始时增量较大,每个子序列中的记录个数较少,从而排序速度较快;当增量较小时,虽然每个子序列中记录个数较多,但整个序列已基本有序,排序速度也较快。,交换排序的主要操作是交换,其主要思想是:在待排序列中选两个记录,将它们的关键码相比较,如果反序(即排列顺序与排序后的次序正好相反),则交换它们的存储位置。,交换排序,反序则 交换,起泡排序,基本思想:两两比较相邻记录的关键码,如果反序则交换,直到没有反序的记录为止。,交换排序,05,98,12,69,38,53,81,起泡排序过程示例,交换排序, 在一趟起泡排序中,若有多个记录位于最终位置,应如何
13、记载? 如何确定起泡排序的范围,使得已经位于最终位置的记录不参与下一趟排序? 如何判别起泡排序的结束?,交换排序,需解决的关键问题?,起泡排序,解决方法: 设变量exchange记载记录交换的位置,则一趟排序后,exchange记载的一定是这一趟排序中记录的最后一次交换的位置,且从此位置以后的所有记录均已经有序。,交换排序,关键问题:如何记载一趟排序过程中交换的多个记录?,交换排序,关键问题:如何记载一趟排序过程中交换的多个记录?,算法描述: if (rjrj+1) rjrj+1; exchange=j; ,解决方法: 设变量exchange记载记录交换的位置,则一趟排序后,exchange记
14、载的一定是这一趟排序中记录的最后一次交换的位置,且从此位置以后的所有记录均已经有序。,解决方法: 设bound位置的记录是无序区的最后一个记录,则每趟起泡排序的范围是r1 rbound。 在一趟排序后,从exchange位置之后的记录一定是有序的,所以bound=exchange。,交换排序,关键问题:如何确定起泡排序的范围?,解决方法: 设bound位置的记录是无序区的最后一个记录,则每趟起泡排序的范围是r1 rbound。 在一趟排序后,从exchange位置之后的记录一定是有序的,所以bound=exchange。,交换排序,关键问题:如何确定起泡排序的范围?,算法描述: bound=e
15、xchange; for (j=1; jrj+1) rjrj+1; exchange=j; ,解决方法: 在每一趟起泡排序之前,令exchange的初值为0,在以后的排序过程中,只要有记录交换,exchange的值就会大于0。这样,在一趟比较完毕,就可以通过exchange的值是否为0来判别是否有记录交换,从而判别整个起泡排序的结束。,交换排序,关键问题:如何判别起泡排序的结束?,解决方法: 在每一趟起泡排序之前,令exchange的初值为0,在以后的排序过程中,只要有记录交换,exchange的值就会大于0。这样,在一趟比较完毕,就可以通过exchange的值是否为0来判别是否有记录交换,从
16、而判别整个起泡排序的结束。,交换排序,关键问题:如何判别起泡排序的结束?,算法描述: while (exchange) 执行一趟起泡排序; ,void BubbleSort(int r , int n) exchange=n; while (exchange) bound=exchange; exchange=0; for (j=1; jrj+1) rjrj+1; exchange=j; ,起泡排序算法,交换排序,起泡排序的时间性能分析,最好情况(正序):,交换排序,时间复杂度为O(n)。,最坏情况(反序):,起泡排序的时间性能分析,最好情况(正序):,交换排序,时间复杂度为O(n);,时间复
17、杂度为O(n2)。,平均情况:时间复杂度为O(n2)。,交换排序,如何改进起泡排序?,造成不对称的原因是什么?,交换排序,如何改变不对称性?,在排序过程中交替改变扫描方向双向起泡排序,快速排序,改进的着眼点:在起泡排序中,记录的比较和移动是在相邻单元中进行的,记录每次交换只能上移或下移一个单元,因而总的比较次数和移动次数较多。,交换排序,减少总的比较次数和移动次数,增大记录的比较和移动距离,较大记录从前面直接移动到后面 较小记录从后面直接移动到前面,快速排序的基本思想,首先选一个轴值(即比较的基准),通过一趟排序将待排序记录分割成独立的两部分,前一部分记录的关键码均小于或等于轴值,后一部分记录
18、的关键码均大于或等于轴值,然后分别对这两部分重复上述方法,直到整个序列有序。,交换排序,如何选择轴值? 如何实现分割(称一次划分)? 如何处理分割得到的两个待排序子序列? 如何判别快速排序的结束?,需解决的关键问题?,选择轴值的方法: 1.使用第一个记录的关键码; 2.选取序列中间记录的关键码; 3.比较序列中第一个记录、最后一个记录和中间记录的关键码,取关键码居中的作为轴值并调换到第一个记录的位置; 4.随机选取轴值。,交换排序,关键问题:如何选择轴值?,选取不同轴值的后果: 决定两个子序列的长度,子序列的长度最好相等。,13,65,27,50,38,49,55,交换排序,关键问题:如何实现
19、一次划分?,解决方法: 设待划分的序列是rs rt,设参数i,j分别指向子序列左、右两端的下标s和t,令rs为轴值, (1)j从后向前扫描,直到rjri,将rj移动到ri的位置,使关键码小(同轴值相比)的记录移动到前面去; (2)i从前向后扫描,直到rirj,将ri移动到rj的位置,使关键码大(同轴值比较)的记录移动到后面去; (3)重复上述过程,直到i=j。,交换排序,关键问题:如何实现一次划分?,交换排序,关键问题:如何实现一次划分?,算法描述:,int Partition(int r , int first, int end) i=first; j=end; /初始化 while (ij
20、) while (ij /i为轴值记录的最终位置 ,解决方法: 对分割得到的两个子序列递归地执行快速排序。,交换排序,关键问题:如何处理分割得到的两个待排序子序列?,38,算法描述:,交换排序,关键问题:如何处理分割得到的两个待排序子序列?,void QuickSort (int r , int first, int end ) pivotpos = Partition (r, first, end ); /一次划分 QuickSort (r, first, pivotpos-1); /对前一个子序列进行快速排序 QuickSort (r, pivotpos+1, end ); /对后一个子序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 部分 排序 技术
链接地址:https://www.31doc.com/p-2626879.html