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

        上节我们学习了冒泡排序和希尔排序，本节我们继续学习归并排序和快速排序。

        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)，是一种不稳定的排序法。