内部排序.ppt
《内部排序.ppt》由会员分享,可在线阅读,更多相关《内部排序.ppt(43页珍藏版)》请在三一文库上搜索。
1、数据结构 第十章 内部排序,本章内容 10.1 基本概念 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序,10-3,10.1 基本概念,关键字 是记录(数据元素)中的一个(或多个)字段。通常用作检索和排序记录的依据。 关键字通常可以进行比较操作。,10-4,10.1 基本概念,排序:设含有n个记录的文件R1,R2,.,Rn,其相应的关键字为K1,K2,.,Kn,将记录按关键字值非递减(或非递增)顺序排列的过程,称为排序。 排序的稳定性:对所有的Ki=Kj (ij)(具有相同关键字),若排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称该排序方
2、法是稳定的,反之,称为不稳定的。稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置(即领先关系)是否变化。 排序分类 内部排序:待排序文件的全部记录存放在内存进行的排序,称为内部排序。 外部排序:排序过程中需要进行内外存数据交换的排序,称为外部排序。,10-5,10.1 基本概念,内排序分类: 按排序过程依据的原则分为: 插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分: 简单排序 先进排序 基数排序,10-6,10.2 插入排序,10.2.1 直接插入排序 它是最简单的排序方法 基本思想:依次将每个待排序的记录插入到一个有序子文件的合适位置(有序子
3、文件记录数增1) 例如:已有待排序文件为:45,34,78,12,34,32,29,64。首先将文件的第一个记录,视为有序文件,然后从第二个记录开始,直到最后一个记录,依次将他们插入到有序文件的合适位置。,12,34,32,29,64,45,34,78,10-7,10.2 插入排序,算法分析 直接插入排序的算法简洁,容易实现。从时间来看,排序的基本操作为:比较两个记录的大小和移动记录。其中: 最小比较次数:Cmin = n-1 = O(n) 最大比较次数:Cmax =(2+3+n)=(n+2)(n-1)/2 = O(n2 ) 最小移动次数:Mmin = 0 最大移动次数:Mmax = (2+1
4、 + 3+1 + + n+1) = O(n2) 若待排序记录序列中出现各种可能排列的概率相同,则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和记录移动次数约为 n2/4。因此,直接插入排序的时间复杂度为 o(n2)。,10-8,10.2 插入排序,结论 直接插入排序的效率与待排文件的关键字排列有关; 直接插入排序的时间复杂度为O(n2); 直接插入排序是稳定的(这一点由过程中WHILE语句的条件“”保证的,只有小于才交换)。,10-9,10.2 插入排序,10.2.2 折半插入排序(Binary Insertsort) 由于是在有序子文件中确定插入的位置,因此可用折半查找
5、来代替直接插入排序法中的顺序查找,从而可减少比较次数。 基本思想 设在顺序表中有一个记录序列 R1, R2, , Rn。其中,R1, R2, , Ri-1 是已经排好序的记录。 在插入 Ri 时,利用折半搜索法寻找 Ri 的插入位置。,10-10,i=1 (30) 13 70 85 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,i=8 20 (6 13 30 39 42 70 85 ) 20,i=8 20 (6 13 20 30 39 42 70 85 ),10.2 插入排序,10.2 插入
6、排序,10-11,算法评价 时间复杂度:T(n)=O(n),折半插入排序只能减少排序过程中关键字比较的时间,并不能减少记录移动的时间。 稳定的排序方法,10-12,10.2 插入排序,10.2.3 Shell排序 基本思想:希尔排序(Shells Methool)又称为缩小增量排序,也是一种插入排序方法。它将待排序数据文件分割成若干个较小的子文件,对各个子文件分别进行直接插入排序,当文件达到基本有序时,再对整个文件进行一次直接插入排序。 适用条件 如果待排序文件“基本有序“,即文件中具有特性: ri.key Max rj .key 1jI 的记录数较少 ,则文件中大多数记录不需要进行插入, 因
7、而排序效率可以提高,接近于O(n)。,10-13,10.2 插入排序,例1:设初始关键字为: 第一趟以步长为5分割为5个子文件: R1,R6 R2,R7 R3,R8 R4,R6 R5,R10 对每个子文件进行直接插入排序 第二趟以步长为3对第一趟排序结果分割为3 个子文件: R1,R4,R7,R10 R2,R5,R8 (R3,R6,R9 对每个子文件进行直接插入排序 第三趟以步长为1对第二趟排序结果进行直接插入排序,49 38 65 97 76 13 27 49 55 04,13 27 49 55 04 49 38 65 97 76,原始数据:,第一趟排序:,第二趟排序:,49 49 97,1
8、3 38 55 76,04 27 65,04 13 27 38 49 49 55 65 76 97,第三趟排序:,10-14,10.2 插入排序,例2:对下列数据进行shell排序,步长分别选为4、2、1。,12,34,32,29,64,45,34,78,10-15,10.2 插入排序,增量的取法 最初 shell 提出取 d1 = n/2,d2 = d1/2,直到dt = 1。后来 knuth 提出取di+1 = di/3 +1。还有人提出都取奇数为好,也有人提出各增量互质为好。 算法分析 不稳定 空间代价:O(1) 增量每次除以2递减,时间代价:O(n2) 选择适当的增量序列,可以使得时间
9、代价接近O(n) 增量每次除以2递减”时,效率仍然为O(n2) 问题:选取的增量之间并不互质 间距为2k-1的子序列都是由那些间距为2k的子序列组成的 上一轮循环中这些子序列都已经排过序了,导致处理效率不高,10-16,10.3 交换排序,10.3.1 冒泡排序 冒泡排序是一种简单而且容易理解的排序方法,它和气泡从水中不断往上冒的情况有些类似。 其基本思想 对存放原始数据的数组,按从后往前的方向进行多次扫描,每次扫描称为一趟 (pass)。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时,就互换两个数据。这样,较小的数据就会逐单元向前移动,好象气泡向上浮起一样。 示例,12,34,32
10、,29,64,78,34,45,10-17,10.3 交换排序,算法评价 算法稳定 空间代价:O(1) 时间代价 : 比较次数 : 交换次数最多为O(n2),最少为0,平均为O(n2)。 最大,平均时间代价均为O(n2)。 最小时间代价为O(n):最佳情况下只运行第一轮循环,10-18,10.3 交换排序,10.3.2 快速排序 基本思想 任取某个记录作为基准(通常选文件的第一个记录),将所有关键字不大于它的记录放在它的前面,将所有关键字不小于它的记录放在它的后面; 这样遍历一趟文件后,将文件以该记录为界分为两部分; 然后对各部分重复上述过程,直到每一部分仅剩一个记录为止。 特点:基于分治法的
11、排序:快速、归并。分治策略的实例 BST查找、插入、删除算法 快速排序、归并排序 二分检索 主要思想:划分、求解子问题(子问题不重叠)、综合解,10-19,10.3 交换排序,25 34 45 32 3412 29 64,29,32,64,25,34,最终排序结果:12 25 29 32 34 34 45 64,45,10-20,10.3 交换排序,快速排序算法评价 快速排序算法不稳定。 常用“三者取中”法来选取划分记录,即取首记录rs.key.尾记录rt.key和中间记录r(s+t)/2.key三者的中间值为划分记录。 算法分析 最差情况: 时间代价: O(n2) 空间代价: O(n) 最佳
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 内部 排序
链接地址:https://www.31doc.com/p-2597649.html