排序算法之 - 歸并排序

    這一章節所講的歸并排序,跟希爾排序一樣,也是一種效率很高的排序方法,也同樣采用了分而治之的方法.

歸并排序的基本思想為:先把無序序列一分為二,然後分别對兩邊的序列進行排序,最後再整合兩邊已經排好的序列.下邊已一張圖來展示歸并排序的思想(圖是借用網友的,見做的非常簡潔易懂,便引用之)

從途中我們看到,二分後的兩邊序列,又進行二分歸并處理,直到兩邊的序列不能二分為止.這就是采用的遞歸思想,出口為左右了;兩邊各隻有一個元素,然後再将兩邊的有序序列歸并成最終序列.下邊看代碼了解:

#include <iostream>
#include <string.h>
#include <errno.h>
#include <stdio.h>

using namespace std;

//需要注意的是,這裡的類模闆需要放在頭檔案中去實作,這裡為了直覺,直接放這裡了
template <typename T>
class Sort
{
private:
//合并兩邊的有序序列
static void Merger(T* nArray, int nBegin, int nMid, int nEnd, bool Min2Max=true)
{
    int len = nEnd - nBegin + 1;
    T tmp[len];  //申請一個臨時空間,存放合并後的序列
    int lIndex = nBegin; //左邊有序序列的其實位置
    int rIndex = nMid + 1;//右邊有序序列的起始位置
    int k = 0;  //臨時空間的起始位置
    //分别從二分的左邊第一個元素,右邊的第一個元素開始比較,依次将二者的極值放到臨時空間中
    while( (lIndex <= nMid)&&(rIndex <= nEnd))
    {
        if( Min2Max ? (nArray[lIndex] < nArray[rIndex]):(nArray[lIndex] > nArray[rIndex]))
        {
            tmp[k++] = nArray[lIndex++];
        }
        else
        {
            tmp[k++] = nArray[rIndex++];
        }
    }
    //把左邊剩餘的元素追加到臨時空間中
    while(lIndex <= nMid)
    {
        tmp[k++] = nArray[lIndex++];
    }
    //或者把右邊剩餘的元素追加到臨時空間中
    while(rIndex <= nEnd)
    {
        tmp[k++] = nArray[rIndex++];
    }
    //将臨時空間排好序的元素放到原序列空間中
    for(int i=nBegin, k=0; i<=nEnd; i++)
    {
        nArray[i] = tmp[k++];
    }
}
//歸并排序(注意采用的是遞歸方式)
static void Merger(T* nArray, int nBegin, int nEnd, bool Min2Max = true)
{
    if(nBegin != nEnd)
    {
        int Mid = (nEnd + nBegin)/2;  //将序列一分為二
        Merger(nArray, nBegin, Mid, Min2Max);//對左邊的序列進行歸并排序
        Merger(nArray, Mid+1, nEnd, Min2Max);//對右邊的序列進行歸并排序
        Merger(nArray, nBegin, Mid, nEnd, Min2Max); //合并左右兩邊已經排好序的序列
    }
}
public:
static void Merger(T* nArray, int nLen, bool Min2Max = true)
{
    Merger(nArray, 0, nLen-1, Min2Max);
}
};

int main(int argc, char* argv[])
{
    int array[] = {12,32,2,4,6,54,13,34,25,87,76,89,32,14,23};
    int len = sizeof(array)/sizeof(int);
    Sort<int>::Merger(array, len);
    for(int i=0; i<len; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}
           

編譯測試