为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； //修改子文件长度 } }