歸并排序和快速排序（三十二）

        上節我們學習了冒泡排序和希爾排序，本節我們繼續學習歸并排序和快速排序。

        1、歸并排序：將兩個或兩個以上的有序序列合并成一個新的有序序列。如下

        那么既然有 2 路歸并，便會有多路歸并。將 3 個有序序列歸并為一個新的有序序列，稱為 3 路歸并；將 N 個有序序列歸并為一個新的有序序列，成為 N 路歸并；將多個有序序列歸并為一個新的有序序列，稱為多路歸并。

        下來我們來看看 2 路歸并示例，如下圖所示

        我們來看看它是怎樣實現的，如下所示

        它是通過比較兩個序列的大小來一個個進行比對的。下來我們來看看歸并排序的具體實現，具體源碼如下

#ifndef SORT_H
#define SORT_H

#include "Object.h"

namespace DTLib
{

class Sort : public Object
{
private:
    Sort();
    Sort(const Sort&);
    Sort& operator= (const Sort&);

    template <typename T>
    static void Swap(T& a, T& b)
    {
        T c(a);
        a = b;
        b = c;
    }

    template < typename T >
    static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max)
    {
        int i = begin;
        int j = mid + 1;
        int k = begin;

        while( (i <= mid) && (j <= end) )
        {
            if( min2max ? (src[i] < src[j]) : (src[i] > src[j]) )
            {
                helper[k++] = src[i++];
            }
            else
            {
                helper[k++] = src[j++];
            }
        }

        while( i <= mid )
        {
            helper[k++] = src[i++];
        }

        while( j <= end )
        {
            helper[k++] = src[j++];
        }

        for(i=begin; i<=end; i++)
        {
            src[i] = helper[i];
        }
    }

    template < typename T >
    static void Merge(T src[], T helper[], int begin, int end, bool min2max)
    {
        if( begin < end )
        {
            int mid = (begin + end) / 2;

            Merge(src, helper, begin, mid, min2max);
            Merge(src, helper, mid+1, end, min2max);
            Merge(src, helper, begin, mid, end, min2max);
        }
    }

public:
    template < typename T >
    static void Merge(T array[], int len, bool min2max = true)
    {
        T* helper = new T[len];

        if( helper != NULL )
        {
            Merge(array, helper, 0, len-1, min2max);
        }

        delete[] helper;
    }
};

}

#endif // SORT_H

        測試代碼如下

#include <iostream>
#include "Sort.h"

using namespace std;
using namespace DTLib;

int main()
{
    int array[] = {9, 3, 2, 4, 1, 5, 7, 6, 9, 8};

    Sort::Merge(array, 10);

    for(int i=0; i<10; i++)
    {
        cout << array[i] << endl;
    }
}

        我們來看看運行結果

        我們將上面的參數變為 false，讓它從大到小來進行排序，運行結果如下圖所示

        2、快速排序：任取序列中的某個數據元素作為基準將整個序列劃分為左右兩個子序列。其中左側子序列中所有元素都小于或等于基準元素，右側子序列中所有元素都大于基準元素，基準元素排在這兩個子序列中間。分別對這兩個子序列重復進行劃分，知道所有的數據元素都排在相應位置上為止。

        快速排序示例如下

        我們來看看具體是怎么實現的，如下所示

        我們看到在選取一個數據元素作為基準元素，大于它的放在右邊，小于它的放在左邊。再次在左側子序列中選取一個元素作為基準元素，以此類推。我們來看看具體源碼的實現，如下

#ifndef SORT_H
#define SORT_H

#include "Object.h"

namespace DTLib
{

class Sort : public Object
{
private:
    Sort();
    Sort(const Sort&);
    Sort& operator= (const Sort&);

    template <typename T>
    static void Swap(T& a, T& b)
    {
        T c(a);
        a = b;
        b = c;
    }

    template < typename T >
    static int Partition(T array[], int begin, int end, bool min2max)
    {
        T pv = array[begin];

        while( begin < end )
        {
            while( (begin < end) && (min2max ? (array[end] > pv) : (array[end] < pv)) )
            {
                end--;
            }

            Swap(array[begin], array[end]);

            while( (begin < end) && (min2max ? (array[begin] <= pv) : (array[begin] >= pv)) )
            {
                begin++;
            }

            Swap(array[begin], array[end]);
        }

        array[begin] = pv;

        return begin;
    }

    template < typename T >
    static void Quick(T array[], int begin, int end, bool min2max)
    {
        if( begin < end )
        {
            int pivot = Partition(array, begin, end, min2max);

            Quick(array, begin, pivot-1, min2max);
            Quick(array, pivot+1, end, min2max);
        }
    }

public:
    template < typename T >
    static void Quick(T array[], int len, bool min2max = true)
    {
        Quick(array, 0, len-1, min2max);
    }
};

}

#endif // SORT_H

        測試代碼就是將上面的歸并排序換成快速排序，我們先來看看不加參數，默認情況下，從小到大進行排序的情況，運行結果如下

        再來看看加參數 false，從大到小的排列情況，結果如下所示

        那么功能已經實現了。通過今天對歸并排序和快速排序的學習，總結如下：1、歸并排序需要額外的輔助空間才能完成，空間復雜度為 O(n)；2、歸并排序的時間復雜度為 O(n*logn)，是一種穩定的排序法；3、快速排序通過對遞歸的方式對排序問題進行劃分；4、快速排序的時間復雜度為 O(n*logn)，是一種不穩定的排序法。