49_归并排序和快速排序

关键词：归并排序、快速排序

0. 归并排序

思想：将两个或两个以上的有序序列合并成一个新的有序序列，这种并归的方法称为2路并归。
将3个有序序列归并成一个新的有序序列称为3路归并；
将N个有序序列归并成一个新的有序序列称为N路归并；
将多个有序序列归并成一个新的有序序列称为多路归并。

2路归并示例
通过递归的方法将无序的序列分解为单个有序序列，然后调用归并排序函数Merge(T scr[], T helper[], int begin, int mid, int end, bool min2max)，实现并归排序。

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. 快速排序

思想：任取序列中某个数据元素作为基准将整个序列划分为左右两个子序列，在左侧子序列中所有元素都小于或等于基准元素，在右侧子序列中所有元素都大于基准元素，基准元素排在这两个子序列中间。分别对这两个子序列重复进行划分，直到所有的数据元素都排在相应位置为止。

快排原理示意图
示例

    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. 小结

• 归并排序需要额外的辅助空间才能完成，空间复杂度为O(n)
• 归并排序的时间复杂度为O(nlogn)，是一种稳定的排序法
• 快速排序通过递归的方式对排序问题进行划分
• 快速排序的时间复杂度为O(nlogn)，是一种不稳定的排序法

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4