9.5归并排序 1、归并排序的基本思想是:将两个(或以上)的 有序表组成新的有序表。(归并排序主要是二路归 并排序) 2、二路归并排序:可以把一个长度为n的无序序 列看成是n个长度为1的有序子序列,首先做 两两归并,得到「n/21个长度为2的有序子序 列;再做两两归并,…,如此重复,直到最后得 到一个长度为n的有序序列。 例8:关键字序列T=(21,25,49,25*,93,62, 72,08,37,16,54),请给出归并排序的具体实 现过程
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），请给出归并排序的具体实 现过程
len=1 len=2 l=4 len=8 en=16 整个归并序仅雳g2n趟
2 21 25 49 25* 93 62 72 08 37 16 54 21 25 25* 49 62 93 08 72 16 37 54 16 37 54 21 25 25* 49 08 62 72 93 08 21 25 25* 49 62 72 93 08 16 21 25 25* 37 49 54 62 72 93 len=1 len=2 len=4 len=8 len=16 16 37 54 整个归并排序仅需log2n 趟
次二路归并排序算法的C语言程序 void merge( DataType all, int n, Data Type swap[, int k) /*k为有序子数组的长度,一次排序后的有序子序列存于数组 swap中* i int m=0, ul, 12, 1,j, u2 int1=0;/第一个有序子数组下界为0*/ while(l+k<=n-1) {12=1l+k /*计算第二个有序子数组下界* ul=12-1 /*计算第一个有序子数组上界* 12=(12+k-1<=n-1)?12+k-1:n-1;/*计算第二个有序子数组上界* /*两个有序子数组合并* ul&&j<=u2;m++) t if(ai]. key <=alj]. key) swap]=al
3 一次二路归并排序算法的C语言程序 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 = l2; i <= u1 && j <= u2; m++) { if(a[i].key <= a[j].key) { swap[m] = a[i]; i++; }
else swap[m=ali] j++;} /*子数组2已归并完,将子数组1中剩余的元素存到数组swap中*/ while(i<=ul) swap=a[]; m++ 体子数组1已归并完,将子数组2中剩余的元素存到数组swap中* whilegj<=u2) swap[m]=alj]; m++: j++:) ll=u2+1; /*将原始数组中只够一组的数据元素顺序存放到数组swap中* for(i=ll; i<n; i++, m++) swap[m=al
4 else { swap[m]=a[j]; j++; } } /*子数组2已归并完，将子数组1中剩余的元素存到数组swap中*/ while(i <= u1) { swap[m] = a[i]; m++; i++; } /*子数组1已归并完，将子数组2中剩余的元素存到数组swap中*/ while(j <= u2) { swap[m] = a[j]; m++; j++; } l1 = u2 + 1; } /*将原始数组中只够一组的数据元素顺序存放到数组swap中*/ for(i = l1; i < n; i++, m++) swap[m] = a[i]; }
3、二路归并排序算法分析: 时间效率:O(nlog2n) 因为在递归的归并排序算法中,函数 Merge()做一趟两路归 并排序,需要调用 nerge()函数nm(2lm)≈ o(n/len)次,而 每次 merge()要执行比较O(len)次,另外整个归并过程有 「log2n1“层”,所以算法总的时间复杂度为O(nlog2n) 空间效率:O(m) 因为需要一个与原始序列同样大小的辅助序列。这正是此 算法的缺点。 稳定性:稳定
5 3、二路归并排序算法分析： • 时间效率： O(nlog2n) 因为在递归的归并排序算法中，函数Merge( )做一趟两路归 并排序，需要调用merge ( )函数 n/(2len) O(n/len) 次，而 每次merge( )要执行比较O(len)次，另外整个归并过程有 log2n “层” ，所以算法总的时间复杂度为O(nlog2n)。 • 空间效率： O(n) 因为需要一个与原始序列同样大小的辅助序列。这正是此 算法的缺点。 • 稳定性：稳定
9.6基数排序 基数排序的基本思想是: 借助多关键字排序的思想对单逻辑关键字进行排 序。即:用关键字不同的位值进行排序。 要讨论的问题 1.什么是“多关键字”排序?实现方法? 2.单逻辑关键字怎样“按位值”排序?
6 9.6 基数排序 要讨论的问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？ 基数排序的基本思想是： 借助多关键字排序的思想对单逻辑关键字进行排 序。即：用关键字不同的位值进行排序
1.什么是“多关键字”排序?实现方法? 例1:对一副扑克牌该如何排序? 若规定花色和面值的顺序关系为 花色:◆<<<心 面值:2<3<4<5<6<7<8<9<10<J<Q<K<A 则可以先按花色排序,花色相同者再按面值排序; 也可以先按面值排序,面值相同者再按花色排序。 例2:职工分房该如何排序? 我校规定:先以总分排序(职称分+工龄分) 总分相同者,再按配偶总分排序,其次按配偶职 称、工龄、人口.等等排序。 以上两例都是典型的多关键字排序
7 1. 什么是“多关键字”排序？实现方法？ 例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A 则可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。 例2：职工分房该如何排序？ 我校规定：先以总分排序（职称分＋工龄分）； 总分相同者，再按配偶总分排序，其次按配偶职 称、工龄、人口……等等排序。 以上两例都是典型的多关键字排序！
多关键字排序的实现方法通常有两种: 最高位优先法MSD( Most Significant Digit first) 最低位优先法LSD( Least Significant Digit first) 例:对一副扑克牌该如何排序? 答:若规定花色为第一关键字(高位),面值为第二关键字 低位),则使用MSD和ISD方法都可以达到排序目的。 MSD方法的思路:先设立4个花色“箱"”,将全部牌按花色分 别归入4个箱内(每个箱中有13张牌);然后对每个箱中的牌 按面值进行插入排序(或其它稳定算法)。 LSD方法的思路:先按面值分成13堆(每堆4张牌),然后对 每堆中的牌按花色进行排序(用插入排序等稳定的算法)。 熄一想:用哪种方法更快些
8 多关键字排序的实现方法通常有两种： • 最高位优先法MSD (Most Significant Digit first) 例：对一副扑克牌该如何排序？ 答：若规定花色为第一关键字（高位），面值为第二关键字 （低位），则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分 别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌 按面值进行插入排序（或其它稳定算法）。 LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对 每堆中的牌按花色进行排序（用插入排序等稳定的算法）。 想一想：用哪种方法更快些？ • 最低位优先法LSD (Least Significant Digit first)
2.单逻辑关键字怎样“按位值”排序? 思路:设刀个记录的序列为:{,M,…,Vn1},可以把每个 记录V的单关键码K看成是一个组(K,K KP),则其中的每一个分量(1≤/≤d)也可看成是 个关键字。 注1:和=最高位,K=最低位;K共有位,可看成o元组; 注2:每个分量和(1≤j≤d)有ri种取值,则称rli为基数 例1:关键码984可以看成是3元组;基数rdli为10。 (9,8,4) (0,1,…,9 例2:关键码dan可以看成是4元组;基数rli为_26 (d, i, a, n
9 2. 单逻辑关键字怎样“按位值”排序？ 设n 个记录的序列为：{V0 , V1 , …, Vn-1 }，可以把每个 记录Vi 的单关键码 Ki看成是一个d元组（Ki 1 , Ki 2 , …, Ki d），则其中的每一个分量Ki j ( 1 j d ) 也可看成是 一个关键字。 4 注1： Ki 1＝最高位，Ki d＝最低位；Ki共有d位，可看成d元组； 注2： 每个分量Ki j (1 j d ) 有radix种取值，则称radix为基数。 26 (9, 8, 4) (0, 1, …, 9) (d, i, a, n) （a, b, …, z） 例1：关键码984可以看成是 3 元组；基数radix 为 10 。 例2：关键码dian可以看成是 元组；基数radix 为 。 思路：
讨论:是借用MSD方式来排序呢,还是借用LSD方式? 例:初始关键字序列T=(32,13,27,32,19,33),请分别 用MSD和LSD进行排序,并讨论其优缺点。 法1(MSD):原始序列:32,13,27,32*,19,33 先按高位M排序:(13,19),27,(32,32*,33) 再按低位排序:13,19,7,32,32,33 因为有尔组,故此算昡需递归实现。 法2(LSD):原始序列:32,13,27,32*,19,33 先按低位好排序:32,32*,13,33,27,19 再按高位和排序:13,19,27,32,32,33 无需分组,易编程实现
10 因为有分组，故此算法需递归实现。 讨论：是借用MSD方式来排序呢，还是借用LSD方式？ 例：初始关键字序列T=（32, 13, 27, 32*, 19，33），请分别 用MSD和LSD进行排序，并讨论其优缺点。 法1（MSD）：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki 1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki 2 排序 ： 13, 19 ， 27, 32, 32*, 33 法2（LSD）： 原始序列： 32, 13, 27, 32*, 19 ，33 先按低位Ki 2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki 1排序： 13, 19 , 27, 32, 32*, 33 无需分组，易编程实现！