算法---歸並排序(Merge Sort)---多版本對比

歸並排序是一種利用“分治”手段來實現的排序方法，其通過二分將數組分為若干個有序的子數組，然後再將這些子數組合並到一起組成一個新的數組。

歸並排序的實現 http://www.linuxidc.com/Linux/2014-09/107316.htm

直接插入排序的三種實現 http://www.linuxidc.com/Linux/2014-09/107313.htm

直接選擇排序及交換二個數據的正確實現 http://www.linuxidc.com/Linux/2014-09/107315.htm

排序總結之選擇式排序  http://www.linuxidc.com/Linux/2014-09/106564.htm

算法的具體實現：

void sort::merge_sort(int* a, const int low, const int high)
{
 if(low>= high)
  return;
 int mid = (low+high)/2;
 merge_sort(a,low,mid);
 merge_sort(a,mid+1,high);
 merge(a,low,mid,high);
}

上述實現可以看出，此算法通過遞歸將數組分為若干個有序的小數組，然後再使用merge方法將這些小數組進行合並，從而完成數組的排序。

merge方法的實現

void sort::merge(int*a ,const int low,const int mid, const int high)
{
 if(a[mid]<=a[mid+1])
  return ;
 int* copy_a = new int[high-low+1];
 for(int i=low; i<=high; i++)
  copy_a[i-low] = a[i];
 int i=low;
 int j=mid+1;
 for(int k=low; k<=high; k++)
 {
  if(i>mid)
  {
   a[k] = copy_a[j-low];
   j++;
  }
  else if(j>high)
  {
   a[k] = copy_a[i-low];
   i++;
  }
  else if(copy_a[i-low]>copy_a[j-low])
  {
   a[k] = copy_a[j-low];
   j++;
  }
  else
  {
   a[k] = copy_a[i-low];
   i++;
  }
 }
 delete[] copy_a;
}

上述實現可以看出，其實就是將兩個有序的數組合並到一個新的數組中而已。

算法的時間復雜度分析，假設有N個數，使用歸並排序所需的時間為T(N)，則從算法的實現可以看出，對N個數排序，需要先分別對左右兩邊的N/2個數排序，時間為2T(N/2)，然後再將排序的兩個數組合並，所需時間為N，因此可得T(N) = 2*T(N/2)+N，計算可得T(N)=NlogN。

上述算法可有改進的地方。顯然是有的。

首先，如果使用歸並排序來排序較小的數組的話，其算法性能沒有之前所說的插入排序好（插入排序算法實現），為此可以設定一個阈值，再使用歸並排序的過程中如果子數組的元素個數小於這個阈值時，使用插入排序來對相應的子數組進行排序。

算法實現：

void sort::merge_sort_update1(int* a, const int low, const int high)
{
 if((high-low + 1) < N)
 {
  for(int i=low+1; i<=high; i++)
  {
   int j=i;
   int temp = a[i];
   for(; j>low && temp < a[j-1]; j--)
   {
    a[j] = a[j-1];
   }
   a[j] = temp;
  }
  return;
 }
 int mid = (low + high)/2;
 merge_sort_update1(a,low,mid);
 merge_sort_update1(a,mid+1,high);
 merge(a,low,mid,high);
}

上述算法改進之後性能上比原來的歸並排序稍好，但是算法的時間復雜度仍然為O(NlogN)。

能否再進一步改進呢？

觀察發現，歸並排序始終使用一個備份數組來存儲排序後的元素，然後再將排序後的元素復制到原來的數組中。在數組新建的過程中將會花費大量的時間。為此可以在這個方面改進一下。可以使用一個實現建好的數組，然後只需使用賦值運算即可，避免了不必要的數組的新建與刪除，從而加快了算法的執行速度。

算法實現：

void sort::merge_sort_update2(int* a, const int low, const int high, int* copy_a)
{
 if(low>=high)
  return;
 int mid = (low+high)/2;
 merge_sort_update2(a,low,mid,copy_a);
 merge_sort_update2(a,mid+1,high,copy_a);
 merge_update2(a,low,mid,high,copy_a);
 for(int i=low; i<=high; i++)
  copy_a[i] = a[i];
}

void sort::merge_update2(int*a ,const int low,const int mid, const int high,const int * copy_a)
{
 if(a[mid] <= a[mid+1])
  return;
 int i=low;
 int j=mid+1;
 for(int k=low; k<=high; k++)
 {
  if(i>mid)
   a[k] = copy_a[j++];
  else if(j>high)
   a[k] = copy_a[i++];
  else if(copy_a[i] > copy_a[j])
   a[k] = copy_a[j++];
  else
   a[k] = copy_a[i++];
 }
}

上述僅僅是自己在學習歸並排序過程中實現的一些想法，如有不足之處還請多多指出，歡迎討論。