2

我认为我下面的实现是有效的，但显然不是。关于使用这种快速排序实现有什么问题的任何想法std::partition？我有一个使用 nth_element 版本的版本，它的代码非常相似和简单。

template <typename It>
void quickSort (const It& lowerIt, const It& upperIt)
{
  auto d = upperIt  - lowerIt ;
  if ( d < 2 )
   return;

  auto midIt = lowerIt + d / 2;

  using T = typename std::iterator_traits<It>::value_type;

  T midValue = *midIt;

  auto pIt = std::partition ( lowerIt, upperIt, [midValue](T i) { return i < midValue; } );

  quickSort( lowerIt, pIt );
  quickSort( pIt + 1, upperIt );
}

使用分区：

前：

83、86、77、15、93、35、86、92、49、21、

后：

21, 15, 77, 35, 49, 83, 86, 92, 86, 93,

4

2 回答 2

7

不能保证枢轴元素位于 location pIt。在大多数情况下，它不会。所以，你应该改变你的算法如下：

  • 选择一个枢轴元素
  • 交换枢轴元素*std::prev(upperIt)
  • std::partition在范围内使用[lowerIt, std::prev(upperIt))
  • 交换pIt_*std::prev(upperIt)
  • 像在你的代码中那样递归调用快速排序

这是您的代码的固定版本：

template <typename It>
void quickSort(It lowerIt, It upperIt)
{
    using std::swap;
    auto size = std::distance(lowerIt, upperIt);
    if (size > 1) {
        auto p = std::prev(upperIt);
        swap(*std::next(lowerIt, size / 2), *p);
        auto q = std::partition(lowerIt, p, [p](decltype(*p) v) { return v < *p; });
        swap(*q, *p);
        quickSort(lowerIt, q);
        quickSort(std::next(q), upperIt);
    }
}
于 2013-10-08T20:27:43.667 回答
1

您的代码有几个严重的问题。让我们单独考虑它们。

首先，如果您选择作为枢轴的项目恰好是集合中最小的，您将获得无限递归——它将所有元素放入上分区，但是当它尝试对上分区进行排序时，它'会以相同的顺序得到相同的元素，将它们全部放在上层分区中并无限重复。

消除这种情况的最常见方法是使用三个枢轴选择的中值。这（几乎）保证至少有一个项目小于枢轴，一个项目大于枢轴，因此即使在最坏的情况下，您也会在每个分区中至少放置一个项目。唯一的例外是如果您选择的三个项目都相同（在这种情况下，您通常需要/想要重新选择您的枢轴值）。

其次，就像几乎所有使用迭代器的东西一样，std::partition假设一个半开范围——即，第一个迭代器指向范围的开头，第二个迭代器指向刚刚超出范围的结尾。这意味着您希望您的递归调用是：

quicksort(lowerIt, pIt);
quicksort(pIt, upperIt);

从理论上讲，跳过枢轴元素实际上不会伤害任何东西（并且可以用来防止前面的问题），但是当你递归时将一个项目排除在处理之外是非常不寻常的，我通常会避免它。为此，为了避免无限递归，您必须将您的枢轴交换到上分区中的第一个位置，所以这是您在递归调用中传递的内容之外的位置。如果你遗漏了一些其他元素，你会遇到问题，因为你不会对所有元素进行排序。

对于 Quicksort 的“严肃”实现，您可能还需要更改一些其他细节，例如当您的分区大小减少到 20 个项目时停止递归，然后当您这样做时，进行插入对整个收藏品进行分类，以将所有东西都放到最后的安息地（可以这么说）。

同样，为了避免堆栈溢出，您通常希望首先对两个分区中较小的一个进行排序。这确保了堆栈空间永远不会超过 O(log N)。就目前而言，堆栈空间可能是 O(N) 最坏的情况。

于 2013-10-08T21:24:27.327 回答