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

Question

从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);
 }

谢谢.

Answer 1

第一个分区调用将我们的数据集拆分为两个:(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