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) 因为需要一个与原始序列同样大小的辅助序列。这正是此 算法的缺点。 • 稳定性：稳定