c++ - 三向快速排序需要更高的性能

Question

我目前正在尝试实现三分区快速排序。下面的代码工作正常，但运行时间不够。我对数据结构、算法和一般的“深入”编程都不熟悉，所以我尝试摆弄它以使其在更短的时间内工作的尝试基本上没有成功。 (内存性能很好。)

我的直觉是改变主元，但我担心这不是三路快速排序。

#include <iostream>
#include <vector>
#include <cstdlib>

using std::vector;
using std::swap;


int partition3(vector<int> &a, int l, int r) {

    int x = a[l]; 
    int j = l;
    int k = r;
    int i = l+1; 

    while (i <= k) {
        if (a[i] < x) {
          swap(a[i],a[j]);
          j++; 
          i++;
        }
        else if(a[i] > x) {
            swap(a[i],a[k]);
            k--;
        }
        else {
            i++;
        }
    }

    return j;
}

void randomized_quick_sort(vector<int> &a, int l, int r) {

    if (l >= r) {
        return;
    }

    int k = l + rand() % (r - l + 1);
    swap(a[l], a[k]);

    while (l < r) {
        int m = partition3(a, l, r);
        if ((m-l) < (r-m)) {
            randomized_quick_sort(a, l, m - 1);
            l = m + 1; 
        }
        else {
            randomized_quick_sort(a, m + 1, r);
            r = m - 1;
        }
    }
}

int main() {
    int n; 
    std::cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); ++i) {
        std::cin >> a[i];
    }
    randomized_quick_sort(a, 0, a.size() - 1);
    for (size_t i = 0; i < a.size(); ++i) {
        std::cout << a[i] << ' ';
    }
}

Answer 1

排序在现实世界中是一个相当复杂的问题。尝试查看一些有效的实现，例如，由 C++ 标准库的实现提供的那些。探索网络、阅读文章、查看讨论……

一些注意事项:

1. 随机数生成(相对)代价高昂，它会显着降低快速排序的速度。 (但是，它也可以对某些类型的数据执行相反的操作。)
2. 整数除法(相对)非常昂贵，可能比随机数生成还贵。
3. 在实践中很少单独使用纯快速排序。通常，它与插入排序相结合，因为递归调用对于非常小的分区效率低下(阈值通常设置在 8 到 16 个元素之间)。
4. 为了防止快速排序出现最坏情况的复杂性，通常会检查递归级别，如果它超过某个阈值 (2 x log_2(n))，则使用另一种算法(通常是堆排序)对其余数据进行排序。

等等...

更新

另外两个想法:

1. 在多核/众核环境中，并行算法可能会为您提供最佳加速。但是设计并行快速排序绝非易事。大部分复杂性落在高效的并行分区和负载平衡上。 Libstdc++ Parallel Mode 有一个很好的 OpenMP 实现。或者，你也可以查看我的AQsort:https://github.com/DanielLangr/AQsort .
2. 要使快速排序更高效，请使用尾调用消除/优化。它大大减少了所需的调用堆栈空间。