数结 华中科技大学 计犷机学院(12 200=g=
2001 -- 12 --31 华中科技大学 数据结构计算机学院(12)
10.4归并排序 基本思想 把k(k≥2)个有序子文件合并在一起,形成一个新的有序 文件 同时归并k个有序子文件的排序过程称为k路归并排序。 2-路归并排序一归并2个有序子文件的排序 例.将有序文件A和B归并为有序文件C。 A=(2,10,15,18,21,30 B=(5,20,35,40) 按从小至大的次序从A或B中依次取出2,5,10,15,,40, 顺序归并到C中,得 C=(2,5,10,15,18,20,21,30,35,40)
10.4 归并排序 基本思想 把k(k≥2)个有序子文件合并在一起，形成一个新的有序 文件。 同时归并k个有序子文件的排序过程称为k-路归并排序。 2-路归并排序---归并2个有序子文件的排序。 例. 将有序文件A和B归并为有序文件C。 A＝(2,10,15,18,21,30) B＝(5,20,35,40) 按从小至大的次序从A或B中依次取出2,5,10,15,...,40, 顺序归并到C中,得: C＝(2,5,10,15,18,20,21,30,35,40)
一般地,2-路归并过程为 假定文件r[low.high]中的相邻子文件(子表) (r[low, r[low+11,., r[mid])FA(r[mid+1],., r Chigh 为有序子文件,其中:1ow≤mid<high 将这两个相邻有序子文件归并为有序文件y[low.high],即: (y [low], y[low+1],., y high] r[9..16 [9..16] 906 k→906 有序 1008 1007 子表 1115 11108 12|40 2|09 1310 2-路归并 1315 有序文件(表 有序 14109 20 子表 15 20 22 1622 16490
一般地，2-路归并过程为： 假定文件r[low..high]中的相邻子文件(子表) (r[low],r[low+1],...,r[mid])和(r[mid+1],...,r[high]) 为有序子文件,其中:low≤mid<high 。 将这两个相邻有序子文件归并为有序文件y[low..high],即： (y[low],y[low+1],...,y[high]) 06 08 15 40 07 09 20 22 r[9..16] 9 10 11 12 13 14 15 16 06 07 08 09 15 20 22 40 y[9..16] 9 10 11 12 13 14 15 16 2-路归并 有序文件(表) i→ j→ k→ 例 有序 子表 有序 子表
将两个有序子文件归并为有一个有序文件的算法 void merge(r, y, low, mid, high) RecType r[,y[; int low, mid, high t int k=i=low, j=mid+ while (i=mid & j<=high I if (rli]. key=rLj]. key) t ykk]=rlij //归并前一个子文件的记录 i+;} else i ykk]=rljl //归并后一个子文件的记录 + k + while(j-high)//归并后一个子文件余下的记录 i ykk]=rlj; j++; k
将两个有序子文件归并为有一个有序文件的算法 void merge(r,y,low,mid,high) RecType r[],y[]；int low,mid,high； { int k=i=low,j=mid+1； while (i<=mid && j<=high) { if (r[i].key<=r[j].key) { y[k]=r[i]； //归并前一个子文件的记录 i++；} else { y[k]=r[j]； //归并后一个子文件的记录 j++；} k++； } while (j<=high) //归并后一个子文件余下的记录 { y[k]=r[j]； j++； k++； }
while(i<=mid)//归并前一个子文件余下的记录 I yLk]rlij i++:k++ merge 2-路归并排序 假定文件(r[1],r[2],,r[n])中记录是随机排列的,进行 2-路归并排序,首先把它划分为长度均为1的n个有序子文件, 然后对它们逐步进行2一路归并排序。其步骤如下 第1趟:从r[1..n]中的第1个和第2个有序子文件开始,调用 算法 merge,每次归并两个相邻子文件,归并结果放到y[1..n]中 在y中形成「n/21个长度为2的有序子文件。若n为奇数,则y中最 后一个子文件的长度为1 第2趟:把y[1.n看作输入文件,将「n/21个有序子文件两 两归并,归并结果回送到r[1..n中,在r中形成「n/212个长度
while (i<=mid) //归并前一个子文件余下的记录 { y[k]=r[i]； i++； k++； } } // merge 2-路归并排序 假定文件(r[1],r[2],...,r[n])中记录是随机排列的,进行 2-路归并排序，首先把它划分为长度均为1的n个有序子文件， 然后对它们逐步进行2－路归并排序。其步骤如下： 第1趟：从r[1..n]中的第1个和第2个有序子文件开始,调用 算法merge,每次归并两个相邻子文件,归并结果放到y[1..n]中。 在y中形成 n/2 个长度为2的有序子文件。若n为奇数,则y中最 后一个子文件的长度为1。 第2趟：把y[1..n]看作输入文件,将 n/2 个有序子文件两 两归并,归并结果回送到r[1..n]中,在r中形成 n/2/2个长度