std :: partition快速排序实现

Question

我认为下面的实现工作但显然没有.关于使用这种快速排序实现有什么问题的任何想法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,

Answer 1

不能保证,枢轴元件将位于该位置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);
    }
}