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

        上節(jié)我們學習了冒泡排序和希爾排序，本節(jié)我們繼續(xù)學習歸并排序和快速排序。

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

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

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

        我們來看看它是怎樣實現(xiàn)的，如下所示

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

#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;
    }
}

        我們來看看運行結(jié)果

        我們將上面的參數(shù)變?yōu)?false，讓它從大到小來進行排序，運行結(jié)果如下圖所示

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

        快速排序示例如下

        我們來看看具體是怎么實現(xiàn)的，如下所示

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

#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

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

        再來看看加參數(shù) false，從大到小的排列情況，結(jié)果如下所示

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