goal00001111

歸并排序算法以O（nlogn）最壞情形運行時間運行，而所使用的比較次數幾乎是最優的。它可以用遞歸的形式實現，形式簡潔易懂。但是需要注意的是當用遞歸形式時，如果數據較多，則開銷很大，實用性很差，所以我們一般采用非遞歸的形式。我這里兩種形式都給出。
      不管是遞歸還是非遞歸，歸并排序算法中基本的操作是合并兩個已經排序的數組。
遞歸形式：
template <class T>
void MSort(T a[], int left, int right)
{
      if (left < right)
      {
            int center = (left + right) / 2;
            MSort(a, left, center);
            MSort(a, center+1, right);
            Merge(a, left, center, right, right-left+1);
      }
}

template <class T>
void MergeSort(T a[], int n)
{
      MSort(a, 0, n-1);
}
///////////////////////////////////////////////////////////////////////
非遞歸形式：
算法介紹：先介紹三個變量beforeLen，afterLen和i的作用：
int beforeLen; //合并前序列的長度
int afterLen;//合并后序列的長度，合并后序列的長度是合并前的兩倍
int i = 0;//開始合并時第一個序列的起始位置下標，每次都是從0開始
i，i+beforeLen-1，i+afterLen-1定義被合并的兩個序列的邊界。
算法的工作過程如下：
開始時，beforeLen被置為1，i被置為0。外部for循環的循環體每執行一次，都使beforeLen和afterLen加倍。內部的while循環執行序列的合并工作，他的循環體每執行一次，i都向前移動afterLen個位置。當n不是afterLen的倍數時，如果被合并序列的起始位置i，加上合并后序列的長度afterLen，超過輸入數組的邊界n，就結束內部循環；此時如果被合并序列的起始位置i，加上合并前序列的長度beforeLen，小于輸入數組的邊界n，還需要執行一次合并工作，把最后長度不足afterLen，但超過beforeLen的序列合并起來。這個工作由算法的語句Merge(a, i, i+beforeLen-1, n-1, n);完成。

template <class T>
void MergeSort(T a[], int n)
{
      int beforeLen; //合并前序列的長度
      int afterLen = 1;//合并后序列的長度
      
      for (beforeLen=1; afterLen<n; beforeLen=afterLen)
      {
            int i = 0;//開始合并時第一個序列的起始位置下標，每次都是從0開始
            afterLen = 2 * beforeLen; //合并后序列的長度是合并前的兩倍
            
            while (i+afterLen < n)
            {
                  Merge(a, i, i+beforeLen-1, i+afterLen-1, afterLen);
                  i += afterLen;
            }
            
            if (i+beforeLen < n)
                  Merge(a, i, i+beforeLen-1, n-1, n);
      }
}
///////////////////////////////////////////////////////////
      上面兩種算法都要用到下面的合并函數。
/*函數介紹：合并兩個有序的子數組
輸入：數組a[]，下標left，center，right，元素個數n，a[left]~a[center]及a[center+1]~a[right]已經按非遞減順序排序。
輸出：按非遞減順序排序的子數組a[left]~a[right]。
*/
template <class T>
void Merge(T a[], int left, int center, int right, int n)
{
      T *t = new T[n];//存放被排序的元素
      int i = left;
      int j = center + 1;
      int k = 0;

      while (i<=center && j<=right)
      {
            if (a[i] <= a[j])
                  t[k++] = a[i++];
            else
                  t[k++] = a[j++];
      }

      if (i == center+1)
      {
            while (j <= right)
                  t[k++] = a[j++];
      }
      else
      {
            while (i <= center)
                  t[k++] = a[i++];
      }
      //把t[]的元素復制回a[]
      for (i=left,k=0; i<=right; i++,k++)
            a[i] = t[k];

      delete []t;
}