快速排序比 std::sort 慢

Question

我有一个 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 倍）。

知道为什么吗？

如何优化我的代码以做好工作？

Answer 1

您的 QuickSort 实现非常普通。它确实使用随机基准选择，确保没有 "killer" 导致性能下降的输入，因此比绝对基本的 QuickSort 更好。

有许多优化可能会用到，其中：

"Quick Sort" 通常实现为混合排序，对于小于某个固定阈值的分区回退到（比如说）插入排序。一旦进入小分区，快速排序的开销往往会克服其渐近复杂性优势。
通过切换到混合递归/迭代方法，可以最小化最大递归深度并减少函数调用开销，其中在每次分区时，递归地对较小的子数组进行排序，但是代码只是循环对较大的进行排序。
分区时，您可以通过找到交换将 both 放入正确子分区的元素对来减少执行的交换次数，并且交换它们，而不是在交换到一个子分区和交换到另一个子分区之间交替。
想出一种在整个排序过程中重复使用相同随机数源的方法，而不是在每次分区时都实例化一个新随机数源，这可能会有所帮助。

快速排序比 std::sort 慢

QuickSort is slower than std::sort

c++

sorting

quicksort