C语言实现排序算法之归并排序详解

归并排序：将一个无序数组合并成一个有序数组

有两种实现方法：自底向上和自顶向下

1、 自底向上的方法（自底向上的归并排序算法虽然效率较高，但可读性较差。）

（1） 自底向上的基本思想：

自底向上的基本思想是：第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到n/2个长度为2的有序子文件；若n为奇数，则最后一个子文件轮空(不参与归并)。故本趟归并完成后，前logn个有序子文件长度为2，但最后一个子文件长度仍为1；第2趟归并则是将第1趟归并所得到的logn个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。
上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为"二路归并排序"。类似地有k(k>2)路归并排序。

（2） 一趟归并算法
 分析：
在某趟归并中，设各子文件长度为length(最后一个子文件的长度可能小于length)，则归并前R[1..n]中共有 个有序的子文件：R[1..length]，R[length+1..2length]，…

注意：

调用归并操作将相邻的一对子文件进行归并时，必须对子文件的个数可能是奇数、以及最后一个子文件的长度小于length这两种特殊情况进行特殊处理：

① 若子文件个数为奇数，则最后一个子文件无须和其它子文件归并(即本趟轮空)；
② 若子文件个数为偶数，则要注意最后一对子文件中后一子文件的区间上界是n。

具体算法如下：

/*自底向上，这里就不写真正的代码了，从网上copy了*/
void MergePass(SeqList R，int length)
{ //对R[1..n]做一趟归并排序
  int i;
  for(i=1;i+2*length-1<=n;i=i+2*length)
    Merge(R,i,i+length-1,i+2*length-1);
  //归并长度为length的两个相邻子文件
  if(i+length-1<n) //尚有两个子文件，其中后一个长度小于length
    Merge(R,i,i+length-1，n)； //归并最后两个子文件
//注意：若i≤n且i+length-1≥n时，则剩余一个子文件轮空，无须归并
} //MergePass

void MergeSort(SeqList R)
{//采用自底向上的方法，对R[1..n]进行二路归并排序
  int length;
  for(1ength=1;length<n;length*=2) //做 趟归并
    MergePass(R，length); //有序段长度≥n时终止
}