快速排序之 c++实现 --使用迭代器

佚名 6年前 (2019-04-10) 随笔 1381人围观抢沙发百度已收录

使用迭代器和模板可以实现程序的通用性，容器和迭代器的设计成功的将算法和数据结构进行分离。

下面是使用迭代器实现的快速排序的核心代码。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

    cout << "data is: " << endl;
    for_each(first, middle1, [](auto n) {cout << n << " "; }); cout << endl;
    for_each(middle2, last, [](auto n) {cout << n << " "; }); cout << endl;
    
    quicksort(first, middle1);
    quicksort(middle2, last);
    
    return; 
}