5

我有一个简单的快速排序实现：

template <typename IteratorType>
void quicksort(IteratorType begin, IteratorType end)
{
  if (begin != end)
  {
    const auto pivot = *(begin + distance(begin, end) / 2);
    const IteratorType sep = std::partition(begin, end, [pivot](typename IteratorType::value_type v){ return (v < pivot); });

    if (sep != begin)
    {
      quicksort(begin, sep);
    }

    if (sep != end)
    {
      quicksort(sep + 1, end);
    }
  }
}

在 1000000 个元素的数组上测试它大约需要永远（6300 毫秒），然后有时会死于递归，而std::sort需要大约 30 毫秒。

当然，我不希望我糟糕的实现速度如此之快，std::sort但怎么会有如此巨大的差异呢？

我知道std::sort使用比简单的快速排序（我相信它是 introsort）更复杂的东西来防止递归级别和东西走得太远。但是，是否有一些明显的我遗漏的东西可以解释如此巨大的差异？

改变箭头的大小表明差异因子不是恒定的，实际上它似乎在增长n²。

4

2 回答 2

1

假设代码是正确的（快速排序可能很棘手），那么我想最大的区别是当元素数量很少时你没有使用更快的排序。例如，当要排序的元素数量小于某个较小的数字时，通常使用选择排序。

那个 rinky-dink C++11 代码也让我怀疑，尽管我承认对此一无所知。

于 2013-04-28T14:10:45.407 回答
1

首先检查更好的枢轴选择（通常使用 3 的中位数）并消除递归的一个分支以节省堆栈空间。

枢轴选择对整体算法性能的影响最大，因为它在 N*log(n) 和 N^2 之间产生了差异。

于 2013-04-28T14:28:23.353 回答