c++ - 将 std::partition 与快速排序一起使用

Question

下面使用partition的quickSort方法有什么问题？第 N 个元素似乎工作正常，但我认为分区也可以。我看到一个有 2 个分区调用的示例，但我不应该只需要一个吗？

#include <iostream>
#include <algorithm>
#include <iterator>

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

  auto midIt = lowerIt + d / 2;

  std::nth_element ( lowerIt, midIt, upperIt);

  quickSortWorks( lowerIt, midIt );
  quickSortWorks( midIt+1, upperIt );
}


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

  auto midIt = lowerIt + d / 2;

  auto pIt = std::partition ( lowerIt, upperIt, [midIt](int i) { return i < *midIt; } );

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

int main ( )
{
  unsigned int N = 10;
  std::vector<int> v(N);
  // srand (time(nullptr));
  for_each(v.begin(), v.end(), [](int& cur){ cur = rand()%100; });

  std::vector<int> vorig(v);

  auto print_vec = [](std::ostream& out, const std::vector<int>& v) {
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(out, ", "));
    out << std::endl;
  };

  std::cout << " Using Partition: " << std::endl;
  std::cout << " Before: " << std::endl;
  print_vec(std::cout,v);
  quickSort(v.begin(), v.end());
  std::cout << " After: " << std::endl;
  print_vec(std::cout,v);

  v = vorig;
  std::cout << " Using Nth Element: " << std::endl;
  std::cout << " Before: " << std::endl;
  print_vec(std::cout,v);
  quickSortWorks(v.begin(), v.end());
  std::cout << " After: " << std::endl;
  print_vec(std::cout,v);
}

输出:

Using Partition: 
 Before: 
83, 86, 77, 15, 93, 35, 86, 92, 49, 21, 
 After: 
21, 15, 77, 35, 49, 83, 86, 92, 86, 93, 

Using Nth Element: 
 Before: 
83, 86, 77, 15, 93, 35, 86, 92, 49, 21, 
 After: 
15, 21, 35, 49, 77, 83, 86, 86, 92, 93, 

Answer 1

所编写的代码只是意外地起作用，原因如下，

std::partition 通过谓词完成它的工作，前向序列包含计算结果为 true 的元素，其余元素计算结果为 false。这意味着 std::partition 将大于基准的元素和等于基准的元素视为等效。

无法保证序列 [middle,last) 的顺序!

显然这不是您想要的。您希望将等于 pivot 的元素压缩到序列 [middle,last) 的前面。这就是为什么您查看的示例代码使用了第二个分区，以将此排序强加于尾随序列(至少您需要将主元元素置于正确的位置)。

为了清楚起见，

template<typename Ran>
  void quicksort(Ran first, Ran last)
  {
    typedef typename std::iterator_traits<Ran>::value_type value_type;
    if (last - first < 2)
       return;
    Ran middle = first + (last - first)/2;
    // save pivot.
    std::iter_swap(middle, last-1);
    middle = std::partition(first, last-1,
        [last] (const value_type& x) { return x < *(last-1); });
    // restore pivot.
    std::iter_swap(middle, last-1);
    quicksort(first, middle);
    quicksort(middle+1, last);
  }