2

下面使用分区的快速排序方法有什么问题？第 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,
4

4 回答 4

7

所写的代码只是意外地起作用，这就是为什么，

std::partition通过谓词完成其工作，前向序列包含评估为真的元素，其余元素评估为假。这意味着std::partition将大于枢轴的元素和等于枢轴的元素视为等效元素。

不保证按顺序订购[middle,last)！

显然这不是你想要的。您希望将元素压缩到与序列的前面相等的枢轴[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);
  }
于 2015-02-23T20:31:45.673 回答
5

即使使用 lambda 修复，它也不起作用，因为std::partition与 不同std::nth_element，它不会返回适合分治递归的迭代器。

调用的返回值是指向分区“上限”范围内第一个std::partition值的迭代器，其中谓词失败。除非偶然，否则这不会是该范围内“最小”的迭代器。

相比之下，“枢轴”操作std::nth_element恰好实现了这一点，这对于分叉递归也是必需的。

通过仅在第一次迭代中手动操作示例可以看出失败。使用这个包含 10 个元素的测试序列：

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

第一个“枢轴”将是第 6 个元素（在索引 0 + 10/2 = 5 处），即 35。使用标准“小于 35”std::partition将在第一步重新排列数组

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

并返回指向第三个元素的指针 (=77)。很明显，值 77 在算法期间将保持在第三个位置。这显然是错误的。

于 2015-02-08T22:20:20.033 回答
1

我刚刚遇到了同样的问题。经过几个小时的分析，我终于找到了解决方案，瞧！！

正如已经提到std::partition的提议的谓词将数组分为两部分，第一部分由小于枢轴的元素组成，第二部分由大于或等于枢轴的元素组成。但不能保证枢轴将是第二部分中的第一个元素。

嗯，std::stable_partition做的工作。只需将枢轴作为first element并应用 stable_partition。因为它会在分区时保持发生的顺序。现在可以保证枢轴将是第二部分的第一个元素。

PS：不要混淆了两个部分。我用这个词来更清楚地解释事情。

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

  auto pIt = lowerIt;

  auto pValue = *pIt; 

  pIt = std::stable_partition ( lowerIt, upperIt, [pValue](int i) { return i < pValue; } );

  quickSort( lowerIt, pIt );
  quickSort( pIt + 1, upperIt );
}
于 2018-07-10T07:27:26.587 回答
0

您的闭包应该捕获 *midIt 的值，而不是 midIt：数量“*midIt”将在分区期间发生变化。

int midValue = *midIt;
std::partition(lowerIt, upperIt, [midValue](int i)...
于 2013-09-28T23:42:02.223 回答