快速排序

快速排序

该算法的思想是：给定一个列表，选取一个数作为“中间值”，之后将列表中的其他值分成两组，一组大于中间值，一组小于中间值；然后对小于“中间值”的组进行排序，返回排好序的列表，对大于“中间值”的一组进行排序，返回排好序的列表。

顺序版

#include <iostream>
#include <list>
#include <algorithm>

template<typename T>
std::list<T> quick_sort(std::list<T> input) {
    if (input.empty())  {
        return input;
    }
    std::list<T> result;
    result.splice(result.end(), input, input.begin()); // 1.选取列表第一个数作为主元
    auto pivot = *result.begin();
    auto divide_point = std::partition(input.begin(), input.end(),
            [&](const T& t){ return t < pivot;} );
    std::list<T> lower_part;
    lower_part.splice(lower_part.begin(), input, input.begin(), divide_point);
    std::list<T> new_lower( quick_sort(std::move(lower_part)) );
    std::list<T> new_higher( quick_sort(std::move(input)) );
    result.splice(result.begin(), new_lower);
    result.splice(result.end(), new_higher);
    return result;
}


void test() {
    std::list<int> l{5,9,6,11,8,4,5,2,4,2,3};
    auto ret = quick_sort(l);
    for (auto x : ret) {
        std::cout << " " << x;
    }
    std::cout << std::endl;
}

int main() {
    test();    // 2 2 3 4 4 5 5 6 8 9 11
    return 0;

线程强化版

#include <iostream>
#include <list>
#include <future>
#include <algorithm>

template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input) {
    if (input.empty())  {
        return input;
    }
    std::list<T> result;
    result.splice(result.end(), input, input.begin()); // 1.选取列表第一个数作为主元
    auto pivot = *result.begin();
    auto divide_point = std::partition(input.begin(), input.end(),
            [&](const T& t){ return t < pivot;} );
    std::list<T> lower_part;
    lower_part.splice(lower_part.begin(), input, input.begin(), divide_point);

    std::future<std::list<T>> new_lower(  // 2.
        std::async(&parallel_quick_sort<T>, std::move(lower_part)));
    std::list<T> new_higher( parallel_quick_sort(std::move(input)) );

    result.splice(result.end(), new_higher);
    result.splice(result.begin(), new_lower.get());  // 3.
    return result;
}