（本文「分治」「原地分割」等的脉络基本与中文维基百科——快速排序一致，如果真的完全理解了快速排序算法那完全可以略过本文。）

引入

（虽然很想开篇直接正题，但这类内容开头写废话已经快成习惯了，还是写一段吧。）

对于略微了解一些计算机科学的人来说，「快速排序」算法可以说是 “Hello, World!” 级别的东西，属于就连校招生面试都不怎么问的烂大街话题了……咳咳。

然而，可能有不少人第一次接触这种入门级话题的时候都是被动接受。在之后，这些话题就成为了常识的一部分，很少有人会再去思考它们，就像不会有人再从皮亚诺公理开始构建数系一样。

可是，如果没有充分理解这个算法，第一看充满「ijk」「向左找向右找」的代码又很容易不明所以。所以，还是有「再探」的价值的。

「函数式编程」

拥趸们向第一次接触「函数式编程语言」的人介绍的时候，都会展示几个例子来介绍「函数式」的强大之处，快速排序算法的实现通常就是这些例子的一员。

为什么会呢？算法的思想、结果不应该是一样的吗？仅仅写法上的不同究竟会带来哪些差异呢？先来看几个例子。

quicksort [] = []
quicksort (x:xs) = quicksort small ++ [x] ++ quicksort large
    where
        small = [y | y <- xs, y <= x]
        large = [y | y <- xs, y > x]

quicksort([]) -> [];
quicksort([X|XS]) -> quicksort([Y || Y <- XS, Y < X]) ++ [X] ++ quicksort([Y || Y <- XS, Y >= X]).

好吧，这两种 （明明应该没有血缘关系的） 语言写法看起来比较像，没什么对照的意义，不过这里也不再列举额外的例子了。

这种写法已经实现了快速排序算法的基本思想——「分治」，好像它和我们见过的 C、C++、Java 的常见写法不太一样？那再换个常见的语言模仿一下。

def quicksort(array: list) -> list:
    if len(array) < 1:
        return array
    return quicksort([x for x in quicksort[1:] if x < quicksort[0]]) + [quicksort[0]] + quicksort([x for x in array[1:] if x >= array[0]])

Python 也支持列表推导式，所以可以比较到位地模仿上面的风味。如果我们再换一个不支持列表推导式语言呢，比如 C++？为了更清晰的描述思想，避免数据结构带来干扰，我们可以多加一些 STL。

template <typename T, template <typename> typename Container = std::vector,
    typename Compare = std::less<>>
Container<T> quicksort(const Container<T>& v)
{
    if (v.empty())
        return v;
    Container<T> lower{}, higher{}, result{};
    std::copy_if(std::next(v.begin()), v.end(), std::back_inserter(lower),
        [&](const T& t) { return Compare{}(t, *v.begin()); });
    lower = quicksort(lower);
    std::copy_if(std::next(v.begin()), v.end(), std::back_inserter(higher),
        [&](const T& t) { return !Compare{}(t, *v.begin()); });
    higher = quicksort(higher);
    result.insert(result.end(), lower.begin(), lower.end());
    result.insert(result.end(), v.begin(), std::next(v.begin()));
    result.insert(result.end(), higher.begin(), higher.end());
    return result;
}

C++ 不支持很多简易的构造操作，需要自行操作内存，即使是分配在栈上的小对象。它不支持列表推导式，但我们也借助 STL 较为简单清晰的描述了列表推导式所隐含的下层操作。

稍有 C 系语言经验即可看出其性能堪忧。这种写法需要额外分配小段内存，再将它们合并。若这里的 Container 不是 std::vector 而是更为笨重的容器，那算法的性能将会进一步大幅降低。

原地分割——交换

「函数式编程」是并不提倡直接修改内存的编程范式，但如果只过滤、分治、递归，那么用非函数式编程语言也可以清晰描述快速排序算法。

显而易见，由于内存分配开销和通常没有尾递归优化，几乎没有人会用非函数式编程语言像上面那样写排序算法。不希望额外分配内存带来开销，那就需要实现「快速排序」通常要求的另一个要点：「原地分割」。

再用 C++ 写一个吧，同样多加点 STL 风味，参考 std::sort，把迭代器传进去。

template<typename Iterator, typename Compare = std::less<>>
void quicksort(Iterator begin, Iterator end)
{
    assert(begin != end);
    if (std::next(begin) == end)
        return;
    Iterator backward = begin, forward = std::next(begin);
    auto pivot = *begin;
    while (forward != end && backward != end) {
        if (Compare{}(*forward, pivot)) {
            std::iter_swap(backward, forward);
            std::advance(backward, 1);
        }
        std::advance(forward, 1);
    }
    if (backward == begin) {
        std::advance(backward, 1);
    }
    quicksort(begin, backward);
    quicksort(backward, end);
}

还算好理解，就不再解读了。这种写法实现了「原地分割」再交换操作，牺牲了一定的可读性，但带来了算法效率的大幅提升。

做了个简单的 benchmark，不「原地分割」版本的 C++ 大约比这个版本慢数百倍，而这版本只比 std::sort 慢一倍左右。至于为什么 std::sort 那么快，那又是另一个话题了……

上述代码的 STL 风味还不是很足，在 cppreference 上发现了更好看的实现。

修改一下，如下。

template <typename ForwardIt, typename Compare = std::less<>>
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 Compare()(em, pivot); });
    ForwardIt middle2 =
        std::partition(middle1, last, [pivot](const auto& em) { return !Compare()(pivot, em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
}