c++ - std::partition 调用两次以进行快速排序

从 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/