华中科技大学：《C语言程序设计》第十章（10-4） 归并排序

数结 华中科技大学 计犷机学院(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个长度

为4的有序子文件。若y中有奇数个子文件,则r中最后一个子文 件的长度为2。 共计经过「log2n趟归并,最后得到n个记录的有序文件 例1.对8个记录作路归并排序,共进行10g281=3趟归并。 1..8] [1..8] 06 06 123 06 02 244 44 10 06 320 310 20 307 410 420 444 408 502 502 502 10 620 620 607 620 708 707 08 720 807 8 08 20 44 第1趟 第2趟 第3趟

为4的有序子文件。若y中有奇数个子文件，则r中最后一个子文 件的长度为2。 ...... 共计经过 log2n 趟归并,最后得到n个记录的有序文件。 例1. 对8个记录作2路归并排序,共进行log28＝3 趟归并。 06 44 20 10 02 20 08 07 １ ２ ３ ４ ５ ６ ７ ８ r[1..８] 06 44 10 20 02 20 07 08 １ ２ ３ ４ ５ ６ ７ ８ y[1..８] 06 10 20 44 02 07 08 20 １ ２ ３ ４ ５ ６ ７ ８ r[1..８] 02 06 07 08 10 20 20 44 １ ２ ３ ４ ５ ６ ７ ８ y[1..８] 第1趟 第2趟 第3趟

例2.对11个记录作2-路归并排序,进行10g211=4趟归并。 [1..11]r[1..11] 106 106 06 244 244 10 123 02 02 06 205 320 20 07 06 410 420 444 08 407 502 02 502 510 08 20 620 607 620 10 08 07 08 20 14 07 808 820 44 20 905 05 905 905 20 1032 1032 10 14 →10 14 1032 14 14 11132 32 44 第1趟 第2趟 第3趟 第4趟

例2. 对11个记录作2-路归并排序,进行log211＝4趟归并。 06 44 20 10 02 20 08 07 05 32 14 1 2 3 4 5 6 7 8 9 10 11 r[1..11] 06 44 10 20 02 20 07 08 05 32 14 y[1..11] 06 10 20 44 02 07 08 20 05 14 32 r[1..11] 02 06 07 08 10 20 20 44 05 14 32 y[1..11] 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 02 05 06 07 08 10 14 20 20 32 44 r[1..11] 1 2 3 4 5 6 7 8 9 10 11 第1趟 第2趟 第3趟 第4趟

趟归并排序算法: //s为子文件的长度,将r中的子文件归并到y中 void mergepass(recType r[], Rec Type y[], int s) i int i=1 while(i+2*s-1=n) //两两归并长度均为s的子文件 I merge(r,y, i, i+s-1, 1+2*s-1) i=i+2*s; if(i+s-1<n)/最后两个子长度为s和长度不足s的文件 merge(r, y, i, its-1, n) else while(i<=n //复制最后一个子文件,长度≤s y[i]=r[i];

一趟归并排序算法： // s为子文件的长度,将r中的子文件归并到y中 void mergepass(RecType r[], RecType y[],int s) { int i=1； while(i+2*s-1<=ｎ) //两两归并长度均为s的子文件 { merge(r,y,i,i+s-1,i+2*s-1)； i=i+2*s； } if (i+s-1<n) //最后两个子长度为s和长度不足s的文件 merge(r,y,i,i+s-1,n)； else while(i<=n) //复制最后一个子文件,长度≤s { y[i]=r[i]； i++； } }

对文件r[1.n归并排序的算法(调用算法 mergepass) void mergesort (Rec Type r[, int n) RecType y [n+1]; int s=l 子文件初始长度为1 while (s<n I mergepass(r, y, s) //将r[1..n]归并到y[1.n] S=2*s; //修改子文件长度 mergepass y,r, s) //将y[1..n]归并到r[1.n S=2*s; //修改子文件长度

对文件r[1..n]归并排序的算法(调用算法mergepass) void mergesort(RecType r[],int n) { RecType y[n+1］； int s=1； //子文件初始长度为1 while (s<n) { mergepass(r,y,s)； //将r[1..n]归并到y[1..n] s=2*s； //修改子文件长度 mergepass(y,r,s)； //将y[1..n]归并到r[1..n] s=2*s； //修改子文件长度 } }

算法分析 ●对n个记录的文件进行归并排序,共需「log2n 趟,每趟所需比较关键字的次数不超过n,共比较 0(nlog2n)次。 ●每趙移动n个记录,共移动0(nlog2n)个记录。 ●归并排序需要一个大小为n的辅助空间y[1..n]。 归并排序是稳定的

算法分析 ● 对n个记录的文件进行归并排序,共需 log2n 趟,每趟所需比较关键字的次数不超过n, 共比较 O(nlog2n)次。 ● 每趟移动n个记录, 共移动O(nlog2n)个记录。 ● 归并排序需要一个大小为n的辅助空间y[1..n]。 ● 归并排序是稳定的