C++快速排序原理深究优化

原创

evenleo

修改于 2020-04-13 11:08:23

7020

修改于 2020-04-13 11:08:23

引言

前面写过一篇关于归并和快排的文章《归并快排算法比较及求第K大元素》，但文中实现的快排算法，在某些极端情况下时间复杂度会退化到 O(n2)，效率将是无法接受的。本文将会把上述退化问题抛出，并进一步深究优化。本文将会进行代码测试，测试将在阿里云1核2G的服务器中进行。

排序测试代码

以下测试代码包括随机生成测试数据和测试排序算法函数，具体作用有注释，不属于本文重点，这里不展开讲。

#include <iostream>
#include <vector>
#include <functional>
#include <string>
#include <cassert>

using namespace std;

namespace sort_helper {
    /*
    * 随机生成 n 个[l, r]的数组
    */
    template <typename T>
    void generate_array(vector<T>& A, int n, int l, int r) 
    {
        assert(l <= r);
        A.reserve(n);
        srand(time(nullptr));
        for (int i = 0; i < n; ++i)
        {
            int e = rand() % (r - l + 1) + l;
            A.push_back(e);
        }
    }

    /*
    * 随机生成近乎有序的 n 个[0, n-1]的数组
    */
    template <typename T>
    void generate_nearly_sorted_array(vector<T>&A, int n, int swap_count)
    {
        for (int i = 0; i < n; ++i)
        {
            A.push_back(i);
        }
        
        srand(time(nullptr));
        for (int i = 0; i < swap_count; ++i) 
        {
            int l = rand() % n;
            int r = rand() % n;
            swap(A[l], A[r]);
        }
    }

    /*
    * 检测数组是否有序
    */
    template <typename T>
    bool is_sorted(vector<T>& A) 
    {
        for (int i = 0; i < A.size()-1; ++i) {
            if (A[i] > A[i+1])
                return false;
        }
        return true;
    }

    /*
    * 测试排序算法，打印算法效率
    */
    template <typename T>
    void testsort(const string& sortname, vector<T>& A,
                  function<void(vector<T>&)> sort_func)
    {
        clock_t start_time = clock();
        sort_func(A);
        clock_t end_time = clock();
        assert(is_sorted(A));
        cout << sortname << ": " 
             << double(end_time - start_time) / CLOCKS_PER_SEC 
             << "s" << endl;
    }
}

归并排序实现

下面是归并排序的实现，用于和下面的快排进行对比，归并排序是每一次平均分成两部分递归进行排序，然后合并，在任意情况下其时间复杂度都是 O(nlogn)，是很稳定的排序算法。这里不对归并排序的原理进行展开，有兴趣的可查看前面提到的文章，这里的实现和那篇文章写的稍有不同，但原理是一样的。

template <typename T>
void merge(vector<T>& A, int l, int mid, int r)
{
    vector<T> aux(r-l+1);
    for (int i = l; i <= r; ++i)
        aux[i-l] = A[i];

    int i = l, j = mid+1;
    for (int k = l; k <= r; ++k)
    {
        if (j > r) {
            A[k] = aux[i-l]; i++;
        } 
        else if (i > mid) {
            A[k] = aux[j-l]; j++;
        } 
        else if (aux[i-l] < aux[j-l]) {
            A[k] = aux[i-l]; i++;
        } 
        else {
            A[k] = aux[j-l]; j++;
        }
    }
}

template <typename T>
void _mergesort(vector<T>& A, int l, int r)
{
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    _mergesort(A, l, mid);
    _mergesort(A, mid+1, r);
    merge(A, l, mid, r);
}

template <typename T>
void mergesort(vector<T>& A)
{
    _mergesort(A, 0, A.size()-1);
}

快速排序原理

核心思想：选取一个基准元素 pivot，比 pivot 小的放到左边，比 pivot 大的放到右边，对 pivot 左右两边的序列递归进行以上操作。

经典快排实现

以下快速排序最容易想到的实现，partition 函数增加基准点随机化的功能，有助于保持算法稳定性。

template <typename T>
int partition(vector<T>& A, int l, int r)
{
    std::swap(A[r], A[rand() % (r-l+1) + l]);  // 基准点随机
    T pivot = A[r];
    int i = l;
    for (int j = l; j < r; ++j)
    {
        if (A[j] < pivot) {
            std::swap(A[i++], A[j]);
        }
    }
    std::swap(A[i], A[r]);
    return i;
}

template <typename T>
void _quicksort(vector<T>& A, int l, int r) 
{
    if (l >= r)
        return;
        
    int p = partition(A, l, r);
    _quicksort(A, l, p-1);
    _quicksort(A, p+1, r);
}

template <typename T>
void quicksort(vector<T>& A) 
{
    srand(time(nullptr));
    _quicksort(A, 0, A.size());
}

经典快排退化

下面用如下三种测试数据分别对归并和快排进行测试，一种是比较分散随机数据，第二种是近乎有序的数据，第三种比较集中的数据：

1000000 个 [0, 1000000] 的数据
1000000 个 [0, 1000000] 近乎有序的数据
1000000 个 [0, 10] 的数据

#include <vector>
#include "sort_helper.h"
#include "mergesort.h"
#include "quicksort.h"
#include "quicksort2.h"
#include "quicksort3.h"

int main()
{
    int n = 1000000;
    vector<int> arr1;
    // 生成含 1000000 个数据在 [0, 1000000] 的数组
    sort_helper::generate_array(arr1, n, 0, n);
    vector<int> arr2(arr1);
    sort_helper::testsort<int>("mergesort", arr1, mergesort<int>);
    sort_helper::testsort<int>("quicksort", arr2, quicksort<int>);

    // 生成含 1000000 个数据在 [0, 1000000] 近乎有序的数组
    vector<int> arr3;
    sort_helper::generate_nearly_sorted_array(arr3, n, 10);
    vector<int> arr4(arr3);
    sort_helper::testsort<int>("mergesort", arr3, mergesort<int>);
    sort_helper::testsort<int>("quicksort", arr4, quicksort<int>);
    
    // 生成含 1000000 个数据在 [0, 10] 的数组
    vector<int> arr5;
    sort_helper::generate_array(arr5, n, 0, 10);
    vector<int> arr6(arr5);
    sort_helper::testsort<int>("mergesort", arr5, mergesort<int>);
    sort_helper::testsort<int>("quicksort", arr6, quicksort<int>);
}

运行结果如下：

generate array: 1000000 number of [0, 1000000]
mergesort: 0.581606s
quicksort: 0.359352s
generate nearly sorted array: 1000000 number of [0, 1000000]
mergesort: 0.443311s
quicksort: 0.267031s
generate array: 1000000 number of [0, 10]
mergesort: 0.490695s
quicksort: 120.131s

非常明显，对于较为分散随机的数据和几乎有序的数据，归并和快排的效率相差不大，快排效率略高，数据比较集中的数据归并排序的效率变化不大，但快排的效率却出现断崖式退化，百万级别的数据已经花了100多秒，更别说千万甚至亿级别的了，这种效率对于海量数据的计算是灾难性的。究其原因，是经典快排的实现是将小于基准 pivot 的数据放在前面，大于等于 pivot 的数据放在后面，然后将基准左右两边的数据进行递归排序，但因为数据过于集中导致等于 pivot 的数据非常多，左右两边的数据非常不平均，右边的数据数量远远大于左边，所以分治的效果 O(logn) 趋向近于 O(n)，效率急剧退化。

二路快排

基于上述经典快排效率退化的分析，只要算法能够将基准两边的数据分配平均，就能挽回排序的效率，所以自然引出了二路快速排序算法，该算法能避免上述因数据过于集中引起的灾难。实现如下：

template <typename T>
int partiton2(vector<T>& A, int l, int r)
{
    std::swap(A[r], A[rand()%(r-l+1) + l]);
    T pivot = A[r];
    int i = l, j = r-1;
    while (true) {
        while (i < r && A[i] < pivot) i++;  // 不能 <=，有等于有可能平衡会倾斜一边
        while (j >= l && A[j] > pivot) j--; // 不能 >=
        if (i > j) break;
        std::swap(A[i++], A[j--]);   // 等于pivot的数据需要平均分配到两边
    }
    std::swap(A[r], A[i]); 
    return i;
}

template <typename T>
void _quicksort2(vector<T>& A, int l, int r)
{
    if (l >= r) 
        return;

    int p = partiton2(A, l, r);
    _quicksort2(A, l, p-1);
    _quicksort2(A, p+1, r);
}

template <typename T>
void quicksort2(vector<T>& A) 
{
    _quicksort2(A, 0, A.size()-1);
}

测试代码如下：

#include <vector>
#include "sort_helper.h"
#include "mergesort.h"
#include "quicksort2.h"

int main()
{
    int n = 1000000;
    vector<int> arr1;
    // 生成含 1000000 个数据在 [0, 1000000] 的数组
    sort_helper::generate_array(arr1, n, 0, n);
    vector<int> arr2(arr1);
    sort_helper::testsort<int>("mergesort", arr1, mergesort<int>);
    sort_helper::testsort<int>("quicksort2", arr2, quicksort2<int>);

    // 生成含 1000000 个数据在 [0, 1000000] 近乎有序的数组
    vector<int> arr3;
    sort_helper::generate_nearly_sorted_array(arr3, n, 10);
    vector<int> arr4(arr3);
    sort_helper::testsort<int>("mergesort", arr3, mergesort<int>);
    sort_helper::testsort<int>("quicksort2", arr4, quicksort2<int>);
    
    // 生成含 1000000 个数据在 [0, 10] 的数组
    vector<int> arr5;
    sort_helper::generate_array(arr5, n, 0, 10);
    vector<int> arr6(arr5);
    sort_helper::testsort<int>("mergesort", arr5, mergesort<int>);
    sort_helper::testsort<int>("quicksort2", arr6, quicksort2<int>);
}

运行结果如下：

generate array: 1000000 number of [0, 1000000]
mergesort: 0.578894s
quicksort2: 0.260607s
generate nearly sorted array: 1000000 number of [0, 1000000]
mergesort: 0.428658s
quicksort2: 0.110484s
generate array: 1000000 number of [0, 10]
mergesort: 0.484847s
quicksort2: 0.204831s

结果非常明显，用二路快速排序算法在数据比较集中的情况下依然能够保持比较高的效率，基本和数据比较分散以及近乎有序的情况下差不多，是比较值得信赖的算法。原因是 partition 函数能将等于 pivot 的数据比较平均的分配给左右两边。

三路快排

上面的二路归并排序能解决经典快排算法 partition 分配数据等于 privot 不均的问题，是一个效率比较稳定的排序算法。但仔细考虑其实还有优化的空间，因为等于 privot 的数据其实已经有序，可以不用加入左右两边进行下面的递归排序。所以自然就引出了三路归并排序算法。三路快速排序算法的原理也非常简单，就是将数据分成三段，分别是小于基数 privot 的数据，等于 privot 的数据，大于 privot 的数据。然后继续递归排序小于和大于 privot 的数据。实现如下：

template <typename T>
void _quicksort3(vector<T>& A, int l, int r)
{
    if (l >= r) 
        return;
    
    int lt = l, gt = r, i = l;

    /* 
    *  [l, lt)    < pivot
    *  [it, i)   == pivot
    *  [gt, r-1]  > pivot
    */
    std::swap(A[r], A[rand()%(r-l+1) + l]);
    T pivot = A[r];
    while (i < gt) {
        if (A[i] < pivot)
            std::swap(A[i++], A[lt++]);
        else if (A[i] > pivot)
            std::swap(A[i], A[--gt]);
        else 
            i++;
    }
    std::swap(A[r], A[gt]);

    _quicksort3(A, l, lt-1);
    _quicksort3(A, gt+1, r);
}

template <typename T>
void quicksort3(vector<T>& A) 
{
    srand(time(nullptr));
    _quicksort3(A, 0, A.size()-1);
}

测试代码如下：

#include <vector>
#include "sort_helper.h"
#include "quicksort2.h"
#include "quicksort3.h"

int main()
{
    int n = 1000000;
    vector<int> arr1;
    // 生成含 1000000 个数据在 [0, 1000000] 的数组
    sort_helper::generate_array(arr1, n, 0, n);
    vector<int> arr2(arr1);
    sort_helper::testsort<int>("quicksort2", arr1, quicksort2<int>);
    sort_helper::testsort<int>("quicksort3", arr2, quicksort3<int>);

    // 生成含 1000000 个数据在 [0, 1000000] 近乎有序的数组
    vector<int> arr3;
    sort_helper::generate_nearly_sorted_array(arr3, n, 10);
    vector<int> arr4(arr3);
    sort_helper::testsort<int>("quicksort2", arr3, quicksort2<int>);
    sort_helper::testsort<int>("quicksort3", arr4, quicksort3<int>);
    
    // 生成含 1000000 个数据在 [0, 10] 的数组
    vector<int> arr5;
    sort_helper::generate_array(arr5, n, 0, 10);
    vector<int> arr6(arr5);
    sort_helper::testsort<int>("quicksort2", arr5, quicksort2<int>);
    sort_helper::testsort<int>("quicksort3", arr6, quicksort3<int>);
}

测试结果如下：

generate array: 1000000 number of [0, 1000000]
quicksort2: 0.263906s
quicksort3: 0.517303s
generate nearly sorted array: 1000000 number of [0, 1000000]
quicksort2: 0.114488s
quicksort3: 0.438819s
generate array: 1000000 number of [0, 10]
quicksort2: 0.207749s
quicksort3: 0.062008s

由上面的测试结果可知，三路快排和二路快排相比，在数据较为集中的情况下，三路快排的效率远远优于二路快排，而且在数据分散随机及数据几乎有序的情况下，三路快排也能保持比较相对不错的效率。因此，可得出初步结论，三路快排不仅在大部分情况下保持不错的效率，而且在数据较为集中的情况下能表现出更为优秀的效率。基于以上原因，三路快排被大部分的系统采用，其实 STL 的排序的核心算法也是采用三路快速排序。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

腾讯云测试服务

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

腾讯云测试服务

登录后参与评论

0 条评论

热度