c++ - QuickSort 比 std::sort 慢

我有一个看起来像这样的 quick_sort 代码(С++)

template< typename BidirectionalIterator, typename Compare >
BidirectionalIterator quick_sort_partition( BidirectionalIterator left, BidirectionalIterator right, Compare cmp ) {
    BidirectionalIterator q = left - 1;
    std::mt19937 gen(time(0));
    std::uniform_int_distribution<int> uid(0, right - left - 1);
    int pivot_1 = uid(gen) ;
    BidirectionalIterator randomNum = pivot_1 + left;
    std::iter_swap( randomNum, right );
    bool index = 0;
    for (BidirectionalIterator i = left; i < right; i++){
        if (*i < *right){
            ++q;
            std::iter_swap( q, i );
        }
        if (*i == *right){
            index = 1 - index;
            if(index){
                ++q;
                std::iter_swap( q, i );
            }
        }
    }

    ++q;
    std::iter_swap( q, right );


    return q;

}
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
    if (first < last){
        BidirectionalIterator q = quick_sort_partition(first, last, cmp);
        quick_sort(first, q - 1, cmp);
        quick_sort(q + 1, last, cmp);
    }
}

但在大型测试中，他比 std::sort 慢(6 倍多)。

任何想法为什么？

如何优化我的代码以获得良好的工作？

最佳答案

您的 QuickSort 实现非常简单。它确实使用随机枢轴选择，确保没有导致性能下降的“杀手”输入，因此比绝对基本的 QuickSort 更好。

可以使用许多优化，其中包括:

“快速排序”实际上是作为一种混合排序来实现的，对于小于某个固定阈值的分区，它回退到(比如说)插入排序。一旦进入小分区，快速排序的开销往往会克服其渐近复杂性的优势。

通过切换到混合递归/迭代方法，可以最小化最大递归深度并减少函数调用开销，其中在每次分区时，较小的子数组被递归排序，但代码只是循环以对较大的子数组进行排序。

分区时，您可以通过查找交换将两个元素都放入正确子分区的元素对并交换它们来减少执行的交换次数，而不是在交换到一个子分区和交换到另一个子分区之间交替。

想出一种在整个排序过程中重用相同随机数源的方法，而不是在每个分区时实例化一个新的随机数源可能会有所帮助。

关于c++ - QuickSort 比 std::sort 慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33156994/