c++标准库中的std::sort算法(及其兄弟std::partial_sort和std::nth_element)在大多数实现中是更基本排序算法的复杂混合组合,例如选择排序、插入排序、快速排序、归并排序或堆排序。
这里和姐妹网站(如https://codereview.stackexchange.com/)上有许多问题与这些经典排序算法实现的错误、复杂性和其他方面有关。大多数提供的实现都由原始循环组成,使用索引操作和具体类型,并且在正确性和效率方面分析起来通常不是简单的。
问:如何使用现代c++实现上面提到的经典排序算法?
没有原始循环,而是结合了<algorithm>中的标准库算法构建块
迭代器接口和使用模板代替索引操作和具体类型
c++ 14风格,包括完整的标准库,以及诸如auto、模板别名、透明比较器和多态lambdas等语法降噪器。
注:
for further references on implementations of sorting algorithms see Wikipedia, Rosetta Code or http://www.sorting-algorithms.com/
according to Sean Parent's conventions (slide 39), a raw loop is a for-loop longer than composition of two functions with an operator. So f(g(x)); or f(x); g(x); or f(x) + g(x); are not raw loops, and neither are the loops in selection_sort and insertion_sort below.
I follow Scott Meyers's terminology to denote the current C++1y already as C++14, and to denote C++98 and C++03 both as C++98, so don't flame me for that.
As suggested in the comments by @Mehrdad, I provide four implementations as a Live Example at the end of the answer: C++14, C++11, C++98 and Boost and C++98.
The answer itself is presented in terms of C++14 only. Where relevant, I denote the syntactic and library differences where the various language versions differ.