在快速排序中使用std :: partition

问题描述

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

What's wrong with the quickSort method using partition below? Nth element seems to work fine but I thought partition would also work. I saw an example that had 2 partition calls but shouldn't I just need one?

#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,

推荐答案

闭包应该捕获* midIt的值，而不是midIt的值：数量

Your closure should capture the value of *midIt, rather than midIt: the quantity "*midIt" will change during partitioning.

int midValue = *midIt;
std::partition(lowerIt, upperIt, [midValue](int i)...

这篇关于在快速排序中使用std :: partition的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！