[經典算法] 歸并排序

題目說明：

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法也是采用分治法（Divide and Conquer）的一個非常典型的應用。算法複雜度為O（N*logN）。

題目解析：

歸并排序是利用遞歸和分而治之的技術将資料序列劃分成為越來越小的半子表，再對半子表排序，最後再用遞歸步驟将排好序的半子表合并成為越來越大的有序序列。

歸并排序包括兩個步驟：

1）劃分子表

2）合并半子表

僞代碼：

合并排序僞代碼(使用哨兵)：
merge(A,p,q,r):
    n1 <—— q-p+1
    n2 <—— r-q
    create array L[0,n1] and R[0,n2]
    for i <—— 0 to n1-1
        do L[i] <—— A[p+i]
    for j <—— 0 to n2-1
        do R[j] <—— A[q+j+1]
    L[n1] <—— +∞
    R[n2] <—— +∞
    i <—— 0
    j <—— 0
    for k i <—— p to r
        do if L[i]<=R[j]
            then A[k]  <—— L[i]
                 i <—— i+1
           else A[k] <—— R[j]
                 j <—— j+1
 
//通過調用merge完成排序：
merge_sort(A,p,r)：
    if p<r
       then q <—— [(p+r)/2] //向下取整
          merge_sort(A,p,q) //分治
          merge_sort(A,q+1,r)
          merge(A,p,q,r)    //合并結果

程式代碼：

#include <gtest/gtest.h>
#include <algorithm>

using namespace std;

template<typename T>
void Merge(T* data, int low, int mid, int high)
{
    T* tmp = new T[high - low + 1];
    int i = low;
    int j = mid + 1;
    int k = 0;

    // 把較小的數先移到新數組中 
    while (i <= mid && j <= high)
    {
        if (data[i] < data[j])
        {
            tmp[k++] = data[i++];
        }
        else
        {
            tmp[k++] = data[j++];
        }
    }

    // 把左邊剩餘的數移入數組  
    while (i <= mid)
    {
        tmp[k++] = data[i++];
    }

    // 把右邊邊剩餘的數移入數組
    while (j <= high)
    {
        tmp[k++] = data[j++];
    }

    // 把新數組中的數覆寫nums數組  
    for (int i = 0; i < k; ++i)
    {
        data[i+low] = tmp[i];
    }

    delete[] tmp;
}

template<typename T>
void MergeSort(T* data, int low, int high)
{
    if (low < high)
    {
        int mid = (low + high)/2;
        // 左邊
        MergeSort(data, low, mid);
        // 右邊 
        MergeSort(data, mid+1, high);
        // 左右歸并
        Merge(data, low, mid, high);
    }
}

template<typename T>
static void ShowElem(T& val)
{
    cout << val << " ";
}

template<typename T>
static bool Validate(T* data, int len)
{
    for (int i=0; i < len-1; ++i)
    {
        if (data[i] > data[i+1])
        {
            return false;
        }
    }

    return true;
}

TEST(Algo, tMergeSort)
{
    int d1[] = {2,8,7,1,3,5,6,4};
    MergeSort(d1, 0, 7);
    for_each(d1, d1+8, ShowElem<int>);
    ASSERT_TRUE(Validate(d1,8));
    cout << endl;

    int d2[] = {2};
    MergeSort(d2, 0, 0);
    for_each(d2, d2+1, ShowElem<int>);
    ASSERT_TRUE(Validate(d2,1));
    cout << endl;

    int d3[] = {2,4,5,6,7,5,2,3,5,7,10,111,2,4,5,6,3,4,5};
    MergeSort(d3, 0, 18);
    for_each(d3, d3+19, ShowElem<int>);
    ASSERT_TRUE(Validate(d3,19));
    cout << endl;
}

運作結果：

參考引用：

http://www.cricode.com/2001.html

http://blog.csdn.net/middlekingt/article/details/8446552

  [經典算法] 歸并排序             
  看書、學習、寫代碼