九章内部排序ppt课件.ppt
《九章内部排序ppt课件.ppt》由会员分享,可在线阅读,更多相关《九章内部排序ppt课件.ppt(39页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、九章内部排序ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望概 述n排序(sorting)n将一个数据元素的任意序列,重新排列成一个按关键字有序的序列。n数据表(datalist)n它是待排序数据对象的有限集合。n关键字(key)n数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据,称为关键字。也称为排序码。n排序方法的稳定性n假设在对象序列中有两 个对象ri和rj,它们的排序码 ki=kj,且在排序之前,对象ri排在
2、rj前面。n如果在排序之后,对象ri仍在对象rj的前面,则称这个排序方法是稳定稳定的,否则称这个排序方法是不稳定不稳定的。n如:n待排序列:49,38,65,97,76,13,27,49n(稳定)排序得到的序列:13,27,38,49,49,65,76,97n内排序与外排序n内排序是指在排序期间数据对象全部存放在内存的排序;n外排序是指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。n排序的时间开销n排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。n内排序分类n依不同原则分n插入排
3、序、交换排序、选择排序、归并排序、和基数排序等。n依所须工作量分n简单排序-时间复杂度O(n2)n先进排序方法-时间复杂度O(nlog2n)n基数排序-时间复杂度O(dn)n排序过程的基本操作:n比较两个关键字的大小n将记录从一个位置移动到另一个位置n待排序记录序列的存储方式:n地址连续的一组存储单元(记录之间的次序关系由存储位置决定,实现排序必须借助移动记录)n静态链表(记录之间的次序关系由指针指示,实现排序不需要移动记录,仅需修改指针)链表排序n地址连续的一组存储单元,另设一个指示各个记录存储位置的地址向量,在排序过程中不移动记录本身,而移动地址向量中的地址,在排序之后再按照地址向量中的值
4、调整记录的存储位置地址排序插入排序n基本思想:n每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。n直接插入排序(Insert Sort)n当插入第i(i 1)个对象时,前面的V0,V1,Vi-1已经排好序。这时,用Vi的排序码与Vi-1,Vi-2,的排序码顺序进行比较,找到插入位置即将Vi插入,原来位置上的对象向后顺移。直直接接插插入入 排排序序过过程程0 1 2 3 4 5 6 i=1i=20 1 2 3 4 5 6212108082525494925*25*16162121250808494925*25*16162121252508
5、08494925*25*16162121252508084925*25*1616 212125250808494925*25*1616i=3212125250808494925*161625*25*212125250808494925*25*1616排序前排序前排序后排序后i=4i=5212125250808494925*25*16161616212125250808494925*25*16162121252508494925*25*1616212125250808494925*25*161608080 1 2 3 4 5 6 n直接插入排序的算法void InsertSort(SqList&
6、L)/按非递减顺序对表进行排序,从后向前顺序比较 for(i=2;i=L.length;+i)if LT(L.ri.key,L.ri-1.key)L.r0=L.ri;for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;/ifn算法分析n设待排序对象个数为 n,则该算法的主程序执行n-1趟。n排序码比较次数和对象移动次数与对象排序码的初始排列有关。n直接插入排序的时间复杂度为 O(n2)。n直接插入排序是一种稳定的排序方法。n折半插入排序(Binary Insertsort)n既然每个要插入记录之前的纪录已经按关键字有序排列,在查
7、找插入位置时就没有必要逐个关键字比较,可以使用折半查找来实现。由此进行的插入排序称之为折半插入排序。n折半插入排序的算法void BInsertSort(SqList&L)for(i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;/查找范围由1到i-1while(low=high+1;-j)L.rj+1=L.rj;/折半查找结束后high+1位置即为插入位置L.rhigh+1=L.r0;/for/BInsertSort折半插入排序折半插入排序0 1 2 3 4 5 6 i=1i=20 1 2 3 4 5 65 521213 33i=355 521215 53
8、 3212144 4i=421215 53 388 8i=521215 53 31616168 84 44 421213 38 84 45 51616n算法分析n折半搜索比顺序搜索查找快,所以折半插入排序就平均性能来说比直接插入排序要快。n它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。n直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同。n折半插入排序的时间复杂度为O(n2)。n折半插入排序是一个稳定的排序方法。交换排序n基本思想:n两两比较待排序对象的排序码,如发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到
9、所有对象都排好序为止。n起泡(冒泡)排序(Bubble Sort)n设待排序对象序列中的对象个数为n。一般地,第i趟起泡排序从1到n-i+1依次比较相邻两个记录地关键字,如果发生逆序,则交换之,其结果是这n-i+1个记录中,关键字最大的记录被交换到第n-i+1的位置上,最多作n-1趟。2 21 10 08 82 25 5 4 49 9 2 25 5 1 16 62 21 14 49 92 25 5 2 25 5 1 16 6 0 08 82 21 14 49 92 25 52 25 51 16 6 0 08 82 21 14 49 92 25 5 2 25 51 16 6 0 08 82 21
10、 14 49 92 25 5 2 25 51 16 6 0 08 8初始关键字第一趟排序第四趟排序第二趟排序第三趟排序2 21 14 49 92 25 5 2 25 51 16 60 08 8第五趟排序起泡排序的过程起泡排序的过程n起泡排序的算法typedef int SortData;void BubbleSort(SortData V,int n)int i=1;int exchange=1;while(i=i;j-)if(Vj-1 Vj)/逆序 Swap(Vj-1,Vj);/交换 exchange=1;/标志置为1,有交换 i+;n算法分析n第i趟对待排序对象序列Vi-1,Vi,Vn-1
11、进行排序,结果将该序列中排序码最小的对象交换到序列的第一个位置(i-1),其它对象也都向排序的最终位置移动。n最多做n-1趟起泡就能把所有对象排好序。n最少只需做1趟n起泡排序是一个稳定的排序方法。n时间复杂度为O(n2)。n快速排序(Quick Sort)n任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列:n左侧子序列中所有对象的排序码都=(或(或=)基准对象的排序码(基准对象也称为枢轴(或支点)记录。)n基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。n然后分别对这两个子序列重复施行上述方法,直到所有的对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 内部 排序 ppt 课件
限制150内