来自 http://en.cppreference.com/w/cpp/algorithm/partition 的示例中对 std::partition 的两次调用背后的逻辑是什么？ ？ 我理解快速排序算法的高级设计，但我很难完全理解这个实现。
template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
谢谢。
最佳答案
第一个分区调用将我们的数据集分成两部分:(1) 小于左侧基准的数据和 (2) 大于或等于右侧基准的数据。
第二个分区将第二个集合 (2) 分成两个集合:(2a) 等于主元的集合和 (2b) 严格大于主元的集合。
然后我们递归 (1) 和 (2b)。基本上，这确保所有等于枢轴的元素都在正确的位置，而不必再次查看。
我不猜测这是否是比规范的单分区实现更好的算法 - 但它就是这样做的。
让我们来看一个例子:
initial array: {3, 4, 5, 3, 4, 6, 4, 1, 4, 8, 8, 1, 6}
↑
pivot
after 1st part: {3, 3, 1, 1, 4, 5, 4, 6, 4, 4, 8, 8, 6}
↑
middle1
after 2nd part: {3, 3, 1, 1, 4, 4, 4, 4, 5, 6, 8, 8, 6}
[-----------) [------------)
recurse ↑ ↑ recurse
↑ ↑
middle1 middle2
关于c++ - std::partition 调用两次以进行快速排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35963436/