归并排序.ppt
《归并排序.ppt》由会员分享,可在线阅读,更多相关《归并排序.ppt(22页珍藏版)》请在三一文库上搜索。
1、1,9.5 归并排序,1、归并排序的基本思想是:将两个(或以上)的有序表组成新的有序表。(归并排序主要是二路归并排序) 2、二路归并排序:可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ,首先做两两归并,得到 n / 2 个长度为 2 的有序子序列 ;再做两两归并,如此重复,直到最后得到一个长度为 n 的有序序列。,例8:关键字序列T= (21,25,49,25*,93,62,72,08,37,16,54),请给出归并排序的具体实现过程。,2,len=1,len=2,len=4,len=8,len=16,整个归并排序仅需log2n 趟,3,一次二路归并排序算法的C语言程序
2、,void Merge(DataType a, int n, DataType swap, int k) /*k为有序子数组的长度,一次排序后的有序子序列存于数组swap中*/ int m = 0, u1,l2,i,j,u2; int l1 = 0; /*第一个有序子数组下界为0*/ while(l1+k = n-1) l2 = l1 + k; /*计算第二个有序子数组下界*/ u1 = l2 - 1; /*计算第一个有序子数组上界*/ u2 = (l2+k-1 = n-1)? l2+k-1: n-1;/*计算第二个有序子数组上界*/ /*两个有序子数组合并*/ for(i = l1, j =
3、 l2; i = u1 ,4,else swapm=aj; j+; /*子数组2已归并完,将子数组1中剩余的元素存到数组swap中*/ while(i = u1) swapm = ai; m+; i+; /*子数组1已归并完,将子数组2中剩余的元素存到数组swap中*/ while(j = u2) swapm = aj; m+; j+; l1 = u2 + 1; /*将原始数组中只够一组的数据元素顺序存放到数组swap中*/ for(i = l1; i n; i+, m+) swapm = ai; ,5,3、二路归并排序算法分析:,时间效率: O(nlog2n),因为在递归的归并排序算法中,函
4、数Merge( )做一趟两路归并排序,需要调用merge ( )函数 n/(2len) O(n/len) 次,而每次merge( )要执行比较O(len)次,另外整个归并过程有log2n “层” ,所以算法总的时间复杂度为O(nlog2n)。 空间效率: O(n) 因为需要一个与原始序列同样大小的辅助序列。这正是此算法的缺点。 稳定性:稳定,6,9.6 基数排序,要讨论的问题: 1. 什么是“多关键字”排序?实现方法? 2. 单逻辑关键字怎样“按位值”排序?,基数排序的基本思想是:,借助多关键字排序的思想对单逻辑关键字进行排序。即:用关键字不同的位值进行排序。,7,1. 什么是“多关键字”排序
5、?实现方法?,例1:对一副扑克牌该如何排序? 若规定花色和面值的顺序关系为: 花色: 面值:2 3 4 5 6 7 8 9 10 J Q K A 则可以先按花色排序,花色相同者再按面值排序; 也可以先按面值排序,面值相同者再按花色排序。,例2:职工分房该如何排序? 我校规定:先以总分排序(职称分工龄分); 总分相同者,再按配偶总分排序,其次按配偶职称、工龄、人口等等排序。,以上两例都是典型的多关键字排序!,8,多关键字排序的实现方法通常有两种:,最高位优先法MSD (Most Significant Digit first),例:对一副扑克牌该如何排序? 答:若规定花色为第一关键字(高位),面
6、值为第二关键字(低位),则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路:先设立4个花色“箱”,将全部牌按花色分别归入4个箱内(每个箱中有13张牌);然后对每个箱中的牌按面值进行插入排序(或其它稳定算法)。 LSD方法的思路:先按面值分成13堆(每堆4张牌),然后对每堆中的牌按花色进行排序(用插入排序等稳定的算法)。,想一想:用哪种方法更快些?,最低位优先法LSD (Least Significant Digit first),9,2. 单逻辑关键字怎样“按位值”排序?,设n 个记录的序列为:V0, V1, , Vn-1 ,可以把每个记录Vi 的单关键码 Ki 看成是一个d元组(
7、Ki1, Ki2, , Kid),则其中的每一个分量Kij ( 1 j d ) 也可看成是一个关键字。,4,注1: Ki1最高位,Kid最低位;Ki共有d位,可看成d元组; 注2: 每个分量Kij (1 j d ) 有radix种取值,则称radix为基数。,26,(9, 8, 4),(0, 1, , 9),(a, b, , z),(d, i, a, n),3,10,思路:,10,因为有分组,故此算法需递归实现。,讨论:是借用MSD方式来排序呢,还是借用LSD方式?,例:初始关键字序列T=(32, 13, 27, 32*, 19,33),请分别用MSD和LSD进行排序,并讨论其优缺点。,法1(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 归并 排序
链接地址:https://www.31doc.com/p-3107051.html