常用排序算法的比较(12)

0。0 第一次写了10KB+的代码略感动。 虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

这个[Num/2]个有序文件的子文件两两归并，如此反复，直到最后得到一个长度为Num的有序文件为止。

MergeSort（） while(len < Num) { MergePass(p, len, Num); len *= 2; }

MergePass

for( i = 1; i+ 2*len-1 <= Num; i = i + 2* len) { Merge( p, i, i+len-1, i+ 2* len -1); }

if( i+ len -1 < Num)//尚有两个子文件，其中最后一个长度小于len { Merge( p, i, i+len-1, Num); }

Merge（） i = low;

j = m +1; k = 0;

q = (int *)malloc(sizeof(int) * high); while( i <= m && j <= high) { q[k++] = p[i] <= p[j]?p[i++]: p[j++]; }

while( i <= m) { q[k++] = p[i++];//将p[low m]中剩余的复制到q中 }

while( j<= high) { q[k++] = p[j++];///将p[m+k high]中剩余的复制到q中 }

for( k = 0, i = low; i<= high; k++, i++) { p[i] = q[k]; //

}//ps：q为p相同类型的指针

算法：在某趟归并中，设各子文件长度为len，则归并前p[1 n]中有[Num/len]个有序子文件。调用递归并操作对子文件进行归并时，必须对子文件的个数可能是奇数、最后一个子文件的长度可能小于len这两种特殊情况进行处理：若子文件个数为奇数，则最后一个子文件无须与其他子文件归并；若子文件个数为偶数，则要注意最后一对子文件中后一个子文件的区间上限为Num。（MergePass）