聲明：版權所有，歡迎轉載。 聯系信箱：[email protected]】
歸並排序Merge sort）的基本思想是合並兩個有序表，設有兩個有序升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸並為一個有序數列，並存儲在A[l..h]。
歸並排序的時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)，空間復雜度為O(N)，它是一種穩定的排序方法。歸並排序在最壞的情況下都是O(NlogN)的時間復雜度，缺點是Merge的時候要有O(N)的額外的空間.
整體來說，對於歸並排序可以運用分而治之方法來解決排序問題，該問題是將n 個元素排成非遞減順序。分而治之方法通常用以下的步驟來進行排序算法：若n 為1，算法終止；否則，將這一元素集合分割成兩個或更多個子集合，對每一個子集合分別排序，然後將排好序的子集合歸並為一個集合。
假設僅將n 個元素的集合分成兩個子集合。現在需要確定如何進行子集合的劃分。一種可能性就是把前面n- 1個元素放到第一個子集中稱為A），最後一個元素放到第二個子集裡稱為B）。按照這種方式對A遞歸地進行排序。由於B僅含一個元素，所以它已經排序完畢，在A排完序後，只需要用程序中的函數insert將A和B合並起來。把這種排序算法與InsertionSort進行比較，可以發現這種排序算法實際上就是插入排序的遞歸算法。該算法的復雜性為O(n2)。把n個元素劃分成兩個子集合的另一種方法是將含有最大值的元素放入B，剩下的放入A中。然後A被遞歸排序。為了合並排序後的A和B，只需要將B添加到A中即可。假如用函數M a x來找出最大元素，這種排序算法實際上就是SelectionSort的遞歸算法。
分治思想：
將原問題分解為幾個規模較小但類似於原問題的子問題，遞歸地求解這些子問題，然後再合並這些子問題的解建立原問題的解，歸並排序完全遵循分治模式：
分解：分解待排序的n個元素的序列成各具n/2個元素的兩個子序列
解決：使用歸並排序遞歸地排序兩個子序列
合並：合並兩個已排序的子序列以產生已排序的答案
歸並排序算法：
歸並排序算法的關鍵操作是“合並”步驟中兩個已排序序列的合並。我們通過調用一個輔助過程merge(A, p, q, r, T)來完成合並，其中A是一個數組，p，q，r是數組下標，滿足p <= q < r， T是一個輔助數組空間。該過程假設子數組A[p..q]和A[q+1..r]都已排好序。它合並這兩個子數組形成單一的已排好的子數組並代替當前的子數組A[p..r]n
過程merge需要O(n)的時間，其中n = r – p + 1是待合並元素的總數。
//將有二個有序數列a[first...mid]和a[mid...last]合並。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
//逐個進行排序，並將排序結果保存在對應的臨時數組中
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
//後半部分已遍歷完，對前半部分剩下的直接拷貝
while (i <= m)
temp[k++] = a[i++];
//前半部分已遍歷完，對後半部分剩下的直接拷貝
while (j <= n)
temp[k++] = a[j++];
//將存放在臨時數組中的數據拷貝到原數組中
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}現在，我們可以過程merge作為歸並排序算法中的一個子程序來用。下面的過程mereg_sort(A, p, r)排序子數組A[p...r]中的元素。若p >= r,則該子數組最多有一個元素，所以已經排好序。否則，分解步驟簡單地計算一個下標q，將A[p...r]分成兩個子數組A[p...q]和A[q...r],前者包含n / 2個元素，後者包含n / 2個元素。
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //對前半部分進行排序
mergesort(a, mid + 1, last, temp); //對後半部分進行排序
mergearray(a, first, mid, last, temp); //合並前後兩部分
}
}
int MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return FALSE;
mergesort(a, 0, n - 1, p);
delete[] p;
return TRUE;
}當然了，每到這個時候我都會說一樣的話，測試程序一定要寫，在程序可控范圍內一定要將測試程序補上。
int main(int argc, char* argv[])
{
int i, array[] = {6, 2, 3, 1, 4, 5};
MergeSort(array, 6);
for (i = 0; i < 6; i++)
{
printf("%d\t", array[i]);
}
getchar();
return 0;
}下一篇貌似該堆排序了，但是對於堆排序我一直不是太懂，大致思路知道，但就是不太理解實際機制，過段時間在寫吧。
本文出自 “驿落黃昏” 博客，請務必保留此出處http://yiluohuanghun.blog.51cto.com/3407300/1271618
