专栏首页C++的沉思C++快速排序原理深究优化
原创

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

引言

前面写过一篇关于归并和快排的文章《归并快排算法比较及求第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());
}

经典快排退化

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

  1. 1000000 个 [0, 1000000] 的数据
  2. 1000000 个 [0, 1000000] 近乎有序的数据
  3. 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 的排序的核心算法也是采用三路快速排序。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 归并快排算法比较及求第K大元素

    核心思想:将数组从中间分成前后两部分,然后对前后两部分分别进行排序,再将排序好的两个部分有序合并在一起,这样整个数组有序。全文图示来源于王争的《数据结构和算法之...

    evenleo
  • 二叉树常见算法总结和C++实现

    DFS深度搜索(从上到下)和分治法区别:前者一般将最终结果通过引用参数传入,或者一般递归返回结果最终合并

    evenleo
  • 从位图原理到布隆过滤器的实现

    假设一个int占4个字节(32位),40个亿个整数就是160亿个字节,大概相当于16GB,假设一台计算机只有2GB内存,则16GB一次加载不完,需要分8次加载,...

    evenleo
  • 算法复杂度分析

    为什么要进行算法分析? 预测算法所需的资源 计算时间(CPU 消耗) 内存空间(RAM 消耗) 通信时间(带宽消耗) 预测算法的运行时间 在给定输入规模时,所执...

    前朝楚水
  • map容器排序

    大忽悠爱学习
  • hdu1014

    @坤的
  • c++之内存模型

    堆区:由程序员分配释放,若程序员不释放,则程序结束时由系统释放。在c++中主要利用new在堆区开辟内存。

    西西嘛呦
  • A+B Problem(V)

    做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

    书童小二
  • 挑战程序竞赛系列(30):3.4矩阵的幂

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Python3 基础学习之数值进制转换

        这个函数在上篇里表示强转,并没有输入n这个参数。当n不输入的时候默认是n=10。

    ZY_FlyWay

扫码关注云+社区

领取腾讯云代金券