相关疑难解决方法(0)

的std::sort算法(及其同类std::partial_sort和std::nth_element从C++标准库)是在大多数实现的更基本的排序算法复杂和混合合并,如选择排序,插入排序,快速排序,归并排序,或堆排序.

这里和姐妹网站上有很多问题,例如https://codereview.stackexchange.com/,与错误,复杂性以及这些经典排序算法的实现的其他方面有关.大多数提供的实现包括原始循环,使用索引操作和具体类型,并且在正确性和效率方面分析通常是非常重要的.

问:如何使用现代C++实现上述经典排序算法？

• 没有原始循环,但结合了标准库的算法构建块<algorithm>
• 迭代器接口和模板的使用,而不是索引操作和具体类型
• C++ 14风格,包括完整的标准库,以及语法降噪器,如auto模板别名,透明比较器和多态lambda.

备注:

• 有关排序算法实现的进一步参考,请参阅Wikipedia,Rosetta Code或http://www.sorting-algorithms.com/
• 根据Sean Parent的惯例(幻灯片39),原始循环for比使用运算符的两个函数的组合更长.所以f(g(x));或f(x); g(x);或f(x) + g(x);不生循环,也不是在环路selection_sort和insertion_sort下方.
• 我遵循Scott Meyers的术语来表示当前的C++ 1y已经作为C++ 14,并且将C++ 98和C++ 03都表示为C++ 98,所以不要因此而激怒我.
• 正如@Mehrdad的评论中所建议的那样,我在答案的最后提供了四个实现作为实例:C++ 14,C++ 11,C++ 98和Boost and C++ 98.
• 答案本身仅以C++ 14的形式呈现.在相关的地方,我表示各种语言版本不同的语法和库差异.