從排序開始（三）歸並排序

歸並排序是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。   歸並操作的過程如下： 1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列 2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置 3.比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置 4.重復步驟3直到某一指針達到序列尾 5.將另一序列剩下的所有元素直接復制到合並序列尾   簡單地說，歸並排序就是將序列不斷地劃分，直到每個序列只有一個元素（一個元素的序列肯定是有序的），然後這些有序序列不斷歸並，合成新的有序序列，最後，歸並成全部有序的序列。   這幅 Wiki 的圖很直觀地解釋了歸並排序：     最差時間復雜度  O(n logn) 最優時間復雜度  O(n) 平均時間復雜度  O(n logn)   穩定性：穩定   實現：  

#include <iostream>  
  
using namespace std;  
  
//歸並操作，將有兩個個有序數列 num[start...mid] 和 num[mid...end] 歸並並。  
//歸並至 sorted 序列，然後復制回原數組  
void merge(int num[], int start, int mid, int end, int sorted[])  
{  
    int i = start, j = mid + 1;  
    int m = mid,   n = end;  
    int k = 0;  
      
    //每次比較兩個元素，直到某個序列到達末尾  
    while (i <= m && j <= n)  
    {  
        if (num[i] <= num[j])  
            sorted[k++] = num[i++];  
        else  
            sorted[k++] = num[j++];  
    }  
      
    //將序列中剩余元素直接復制到 sorted 序列尾  
    while (i <= m)  
        sorted[k++] = num[i++];  
      
    while (j <= n)  
        sorted[k++] = num[j++];  
      
    //將排序好的序列寫回原數組  
    for (i = 0; i < k; i++)  
        num[start + i] = sorted[i];  
}  
  
void mergesort(int a[], int start, int end, int sorted[])  
{  
    if (start < end)  
    {  
        //進行分治  
        int mid = (start + end) / 2;  
        mergesort(a, start, mid, sorted);      
        mergesort(a, mid + 1, end, sorted);   
        merge(a, start, mid, end, sorted);   
    }  
}  
  
bool MergeSort(int num[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(num, 0, n - 1, p);  
    delete[] p;  
    return true;  
}  
  
//簡單測試,建議數據不要太大，那是在刷屏啊 o(╯□╰)o  
int main()  
{  
    int n;  
    //測試 n 個隨機數的排序  
    while(cin>>n)  
    {  
        int *p = new int[n];  
        if (!p)  
        {  
            cout<<"Failed..."<<endl;  
            continue;  
        }  
        for(int i=0;i<n;++i)  
            p[i] = rand();  
        bool flag = MergeSort(p,n);  
        if(!flag)  
        {  
            cout<<"Failed..."<<endl;  
            continue;  
        }  
        for(int i=0;i<n;++i)  
            cout<<p[i]<<' ';  
        cout<<endl;  
        delete []p;  
    }  
    return 0;  
}