排序的基本概念.ppt
《排序的基本概念.ppt》由会员分享,可在线阅读,更多相关《排序的基本概念.ppt(34页珍藏版)》请在三一办公上搜索。
1、1,9.1 排序的基本概念9.2 插入排序9.3 选择排序9.4 交换排序9.5 归并排序9.6 基数排序9.7 性能比较,第9章 排序,2,9.1排序的基本概念,1.排序:将一组杂乱无章的数据按一定的规律顺次排列起来的过程。,存放在数据表中,按关键字排序,2.排序的目的:便于查找。,3.排序算法好坏的衡量标准:(1)时间复杂度 它主要是分析记录关键字的比较次数和记录的移动次数。(2)空间复杂度算法中使用的内存辅助空间的多少。(3)稳定性若两个记录A和B的关键字值相等,但排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。,4、排序的种类:分为内部排序和外部排序两大类。若待排序记录都在内
2、存中,称为内部排序;若待排序记录一部分在内存,一部分在外存,则称为外部排序。,注:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。,3,5.待排序记录在内存中怎样存储和处理?,顺序排序排序时直接移动记录;链表排序排序时只移动指针;地址排序排序时先移动地址,最后再移动记录。,注:地址排序中可以增设一维数组来专门存放记录的地址。,6.内部排序的算法有哪些?,按排序的规则不同,可分为5类:插入排序、交换排序、选择排序、归并排序、基数排序按排序算法的时间复杂度不同,可分为3类:简单的排序算法:时间效率低,O(n2)先进的排序算法:时间效率高,O(nlog2n)
3、基 数 排 序 算法:时间效率高,O(dn),d关键字的位数(长度),4,9.2 插入排序,插入排序的基本思想是:每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。,简言之,边插入边排序,保证子序列中随时都是排好序的。,常用的插入排序有:直接插入排序和希尔排序两种。,一、直接插入排序,1、其基本思想是:顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。,最简单的排序法!,5,初始关键字序列:【13】,6,3,31,9,27,5,11第一次排序:【6,13】,3,31,9,27,5,11第二次排序:【3,6,1
4、3】,31,9,27,5,11第三次排序:【3,6,13,31】,9,27,5,11第四次排序:【3,6,9,13,31】,27,5,11第五次排序:【3,6,9,13,27,31】,5,11第六次排序:【3,5,6,9,13,27,31】,11第七次排序:【3,5,6,9,11,13,27,31】,例1:关键字序列T=(13,6,3,31,9,27,5,11),请写出直接插入排序的中间过程序列。,注:方括号 中为已排序记录的关键字,下划横线的 关键字表示它对应的记录后移一个位置。,6,2、C语言程序,void InsertSort(DataType a,int n)/*用直接插入法对a0-a
5、n-1排序*/int i,j;DataType temp;for(i=0;i-1,7,void main(void)DataType test6=64,5,7,89,6,24;int i,n=6;SeqList myList;ListInitiate(,#include typedef int KeyType;typedef structKeyType key;DataType;#define MaxSize 100#include SeqList.h,8,(1)时间效率:因为在最坏情况下,所有元素的比较次数总和为(01n-1)O(n2)。其他情况下也要考虑移动元素的次数。故时间复杂度为O(n
6、2)(2)空间效率:仅占用1个缓冲单元O(1)(3)算法的稳定性:稳定,3、直接插入排序算法分析,二、希尔(shell)排序(又称缩小增量排序),1、基本思想:把整个待排序的数据元素分成若干个小组,对同一小组内的数据元素用直接插入法排序;小组的个数逐次缩小,当完成了所有数据元素都在一个组内的排序后排序过程结束。2、技巧:小组的构成不是简单地“逐段分割”,而是将相隔某个增量dk的记录组成一个小组,让增量dk逐趟缩短(例如依次取5,3,1),直到dk1为止。3、优点:让关键字值小的元素能很快前移,且序列若基本有序时,再用直接插入排序处理,时间效率会高很多。,9,例2:设待排序的序列中有12个记录,
7、它们的关键字序列 T=(65,34,25,87,12,38,56,46,14,77,92,23),请写出希尔排序的具体实现过程。,算法分析:开始时d 的值较大,子序列中的对象较少,排序速度较快;随着排序进展,d 值逐渐变小,子序列中对象个数逐渐变多,由于前面工作的基础,大多数记录已基本有序,所以排序速度仍然很快。通常,di+1=di/2(结果取整)时间效率:O(n(log2n)2)空间效率:O(1)因为仅占用1个缓冲单元 算法的稳定性:不稳定 下面给出希尔排序的具体实现过程:,10,第1趟(d=6),第2趟(d=3),第3趟(d=1),11,4、C语言程序,void ShellSort(Dat
8、aType a,int n,int d,int numOfD)int i,j,k,m,span;DataType temp;for(m=0;m-1,12,练习:,1.欲将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母升序重排,则初始步长为4的希尔排序一趟的结果是?答:原始序列:Q,H,C,Y,P,A,M,S,R,D,F,X shell一趟后:,2.以关键字序列(256,301,751,129,937,863,742,694,076,438)为例,写出执行希尔排序(取d=5,3,1)算法的各趟排序结束时,关键字序列的状态。,解:原始序列:256,301,751,129,9
9、37,863,742,694,076,438,第1趟d=5第2趟d=3第3趟d=1,256,301,694,076,438,863,742,751,129,937,076,301,129,256,438,694,742,751,863,937,076,129,256,301,438,694,742,751,863,937,希尔排序,13,9.3 选择排序,选择排序的基本思想是:每次从待排序的数据元素集合中选取关键字最小(或最大)的数据元素放到数据元素集合的最前(或最后),数据元素集合不断缩小,当数据元素集合为空时选择排序结束。,常用的选择排序算法:(1)直接选择排序(2)堆排序,14,一、直接
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 基本概念
链接地址:https://www.31ppt.com/p-6226495.html