排序——歸并排序

基本思想：

    首先，将R[1]~R[n]看成n個長度為1的有序表，将相鄰的有序表成對歸并，得到n/2個長度為2的有序表；然後，再将這些有序表成對歸并，得到n/4個長度為4的有序表，如此反複進行下去，得到一個長度為n的有序表。

    （與前面介紹的幾種排序方法不同，歸并排序需要用到一個和R同類型的輔助數組S）

算法關鍵步驟：

    1、定義兩組歸并算法

        merge(list R,list S,int a,int b,int c),

     它将有序表R[a]~R[b]和R[b+1]~R[c]歸并到S[a]~S[c]中

     2、定義一趟歸并算法

        mergepass(list R,list S,int &m)

     它将R中的有序表成對歸并到S中。m是歸并前R中第一個有序表的長度，一趟歸并後m的值*2

     令m的初始值為1，在m<n的情況下，交替調用一趟歸并算法mergepass(R,S,m)和mergepass(S,R,m)

代碼：

//兩組歸并
void merge(list R,list S,int a,int b,int c)
{
  int i,j,k;
  i=a; j=b+1; k=a;
  while((i<=b)&&(j<=c)) 
    if(R[i].key<=R[j].key)
         S[k++]=R[i++];                   
    else S[k++]=R[j++];                           
  while(i<=b) S[k++]=R[i++];                  
  while(j<=c) S[k++]=R[j++]
} 
//一趟歸并          
void mergepass(list R,list S,int &m)         
{                               
  int i=1,j;                     
  while(i+2*m-1<=n){  //相鄰的兩個有序表長度都是m
    merge(R,S,i,i+m-1,i+2*m-1);   
    i=i+2*m;                      
  }                              
  if(i+m-1<n)//剩下兩個有序表，最後一個有序表長度小于m       
     merge(R,S,i,i+m-1,n);         
  else       //剩下一個有序表                         
     for(j=i;j<=n;j++) S[j]=R[j];                   
  m=2*m;                         
}
//歸并排序
void mergesort()         
{                        
  list S;
  int m=1;
  while(m<n) {
    mergepass(R,S,m);
    mergepass(S,R,m);
  }
}
           

算法分析：

    對n個元素進行歸并排序，需要經過log2n趟

歸并，每一趟歸并，其排序碼比較次數不超過n–1，

元素移動次數都是n。

    是以，歸并排序的執行時間是O(nlog2n)。

    歸并排序是穩定的排序。