關(guān)鍵詞：歸并排序哗讥、快速排序

0. 歸并排序

思想：將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)新的有序序列朵栖，這種并歸的方法稱為2路并歸责循。
將3個(gè)有序序列歸并成一個(gè)新的有序序列稱為3路歸并撮珠；
將N個(gè)有序序列歸并成一個(gè)新的有序序列稱為N路歸并歌粥；
將多個(gè)有序序列歸并成一個(gè)新的有序序列稱為多路歸并塌忽。

2路歸并示例

template < typename T >
    static void Merge(T scr[], 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 ? (scr[i] < scr[j]) : (scr[i] > scr[j]))
            {
                helper[k++] = scr[i++];
            }
            else
            {
                helper[k++] = scr[j++];
            }
        }

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

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

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

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

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

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

1. 快速排序

思想：任取序列中某個(gè)數(shù)據(jù)元素作為基準(zhǔn)將整個(gè)序列劃分為左右兩個(gè)子序列，在左側(cè)子序列中所有元素都小于或等于基準(zhǔn)元素，在右側(cè)子序列中所有元素都大于基準(zhǔn)元素装盯，基準(zhǔn)元素排在這兩個(gè)子序列中間坷虑。分別對(duì)這兩個(gè)子序列重復(fù)進(jìn)行劃分，直到所有的數(shù)據(jù)元素都排在相應(yīng)位置為止埂奈。

快排原理示意圖

示例

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

            if( begin != end )
            {
                Swap(array[begin], array[end]);
            }

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

            if( begin != end )
            {
                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);
        }
    }

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

2. 小結(jié)

• 歸并排序需要額外的輔助空間才能完成迄损，空間復(fù)雜度為O(n)
• 歸并排序的時(shí)間復(fù)雜度為O(nlogn)，是一種穩(wěn)定的排序法
• 快速排序通過遞歸的方式對(duì)排序問題進(jìn)行劃分
• 快速排序的時(shí)間復(fù)雜度為O(nlogn)账磺，是一種不穩(wěn)定的排序法

聲明：此文章僅是本人在學(xué)習(xí)狄泰學(xué)院《數(shù)據(jù)結(jié)構(gòu)實(shí)戰(zhàn)開發(fā)教程》所做的筆記芹敌，文章中包含狄泰軟件資料內(nèi)容，一切版權(quán)歸狄泰軟件所有垮抗！
實(shí)驗(yàn)環(huán)境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4