如何在现代C ++中实现经典的sortingalgorithm？

来自C ++标准库的std::sortalgorithm（和它的cousins std::partial_sort和std::nth_element ）在大多数实现中是一个更复杂和更混合的基本sortingalgorithm ，比如selectsorting，插入sorting，快速sorting，合并sorting或堆sorting。

这里和姊妹网站上有许多问题，例如https://codereview.stackexchange.com/与错误，复杂性和这些经典sortingalgorithm实现的其他方面有关。 大多数提供的实现包括原始循环，使用索引操作和具体types，并且通常在正确性和效率方面是非平凡的。

问题 ：如何使用现代C ++实现上述经典sortingalgorithm？

• 没有原始循环 ，但将标准库的algorithm构build块与<algorithm>
• 迭代器接口和使用模板而不是索引操作和具体types
• C ++ 14风格 ，包括完整的标准库，以及句法噪声抑制器，例如auto ，模板别名，透明比较器和多态lambdaexpression式。

备注 ：

• 有关sortingalgorithm实现的进一步参考，请参阅Wikipedia ， Rosetta Code或http://www.sorting-algorithms.com/
• 根据肖恩家长的惯例 （幻灯片39），一个原始循环比一个操作符的两个函数的组合更长。 所以f(g(x)); 或f(x); 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的评论中所build议的那样，我在回答结尾提供了四个实例作为实例：C ++ 14，C ++ 11，C ++ 98和Boost和C ++ 98。
• 答案本身只是以C ++ 14的forms出现的。 在相关的地方，我指出了各种语言版本不同的句法和库的区别。

Answer 1

algorithm构build块

我们从汇编标准库中的algorithm构build块开始：

 #include <algorithm> // min_element, iter_swap, // upper_bound, rotate, // partition, // inplace_merge, // make_heap, sort_heap, push_heap, pop_heap, // is_heap, is_sorted #include <cassert> // assert #include <functional> // less #include <iterator> // distance, begin, end, next 

• 诸如非成员std::begin() / std::end()以及std::next()的迭代器工具仅在C ++ 11及更高版本中可用。 对于C ++ 98，需要自己写这些。 在boost::begin() / boost::end()和boost::next() Boost.Utility中有Boost.Range的替代。
• std::is_sortedalgorithm仅适用于C ++ 11及更高版本。 对于C ++ 98，这可以用std::adjacent_find和一个手写函数对象来实现。 Boost.Algorithm还提供了boost::algorithm::is_sorted作为替代。
• std::is_heapalgorithm仅适用于C ++ 11及更高版本。

语法好的东西

C ++ 14提供了forms为std::less<> 透明比较器 ，这些比较器在其参数上进行多态操作。 这避免了必须提供迭代器的types。 这可以与C ++ 11的默认函数模板参数结合使用，以便为sortingalgorithm创build一个单独的重载 ，这些重排algorithm用于<比较以及具有用户定义的比较函数对象的sortingalgorithm。

 template<class It, class Compare = std::less<>> void xxx_sort(It first, It last, Compare cmp = Compare{}); 

在C ++ 11中，可以定义一个可重用的模板别名来提取一个迭代器的值types，这会给sortingalgorithm的签名增加一些次要的混乱：

 template<class It> using value_type_t = typename std::iterator_traits<It>::value_type; template<class It, class Compare = std::less<value_type_t<It>>> void xxx_sort(It first, It last, Compare cmp = Compare{}); 

在C ++ 98中，需要编写两个重载，并使用详细的typename xxx<yyy>::type语法

 template<class It, class Compare> void xxx_sort(It first, It last, Compare cmp); // general implementation template<class It> void xxx_sort(It first, It last) { xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>()); } 

• 另一个语法上的好处是，C ++ 14通过多态lambdaexpression式 （带有像函数模板参数一样推导的auto参数）方便地包装用户定义的比较器。
• C ++ 11只有单形lambda，需要使用上面的模板别名value_type_t 。
• 在C ++ 98中，需要编写一个独立的函数对象，或者使用详细的std::bind1st / std::bind2nd / std::not1types的语法。
• Boost.Bind通过boost::bind和_1 / _2占位符语法改进了这一点。
• C ++ 11及更高版本也有std::find_if_not ，而C ++ 98需要std::find_if和函数对象的std::not1 。

C ++风格

目前还没有普遍接受的C ++ 14风格。 更糟糕的是，我紧随斯科特·迈耶斯（Scott Meyers）的“ 有效的现代C ++”（Effective Modern C ++）和Herb Sutter的新版“GotW” 。 我使用下面的风格build议：

• Herb Sutter的“几乎总是自动”和斯科特·迈耶斯（Scott Meyers）的“倾向于特定types声明的汽车”的build议，尽pipe它的清晰度有时是有争议的 ，但其简洁性是无与伦比的。
• Scott Meyers的“在创build对象时区分()和{} ”，并且始终select使用braced-initialization {}代替旧的带括号的初始化() （以便旁路所有在通用代码中最棘手的分析问题）。
• Scott Meyers的“首选别名声明” 。 对于模板来说，这是必须的，而不是使用typedef节省时间并增加一致性。
• 我在一些地方使用了for (auto it = first; it != last; ++it)模式，以便对已sorting的子范围进行循环不variables检查。 在生产代码中， while (first != last)和++first在循环内部使用可能会稍微好一点。

selectsorting

selectsorting不适合数据，所以它的运行时间总是O(N^2) 。 然而，select种类具有最小化交换次数的性质 。 在交换项目成本较高的应用中，selectsorting很好可能是select的algorithm。

要使用标准库来实现它，请重复使用std::min_element来查找剩余的最小元素，并使用iter_swap将其交换到位：

 template<class FwdIt, class Compare = std::less<>> void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { for (auto it = first; it != last; ++it) { auto const selection = std::min_element(it, last, cmp); std::iter_swap(selection, it); assert(std::is_sorted(first, std::next(it), cmp)); } } 

请注意， selection_sort具有已经处理的范围[first, it)sorting为它的循环不variables。 与std::sort的随机访问迭代器相比，最小需求是前向迭代器。

细节省略 ：

• if (std::distance(first, last) <= 1) return;则可以使用早期testing来优化selectsortingif (std::distance(first, last) <= 1) return; （或对于正向/双向迭代器： if (first == last || std::next(first) == last) return; ）。
• 对于双向迭代器 ，上面的testing可以在间隔[first, std::prev(last))与循环组合，因为最后一个元素保证是最小的剩余元素，不需要交换。

插入sorting

虽然它是O(N^2)最坏情况时间的基本sortingalgorithm之一，但插入sorting是当数据几乎sorting（因为它是自适应的 ）或问题规模很小（因为它具有低开销）。 由于这些原因，并且因为它也是稳定的 ，所以插入sorting经常被用作recursion基本情况（当问题规模较小时）用于较高开销的分而治之sortingalgorithm，诸如合并sorting或快速sorting。

要使用标准库实现insertion_sort ，请重复使用std::upper_bound来查找当前元素需要的位置，并使用std::rotate在input范围中向上移动其余元素：

 template<class FwdIt, class Compare = std::less<>> void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { for (auto it = first; it != last; ++it) { auto const insertion = std::upper_bound(first, it, *it, cmp); std::rotate(insertion, it, std::next(it)); assert(std::is_sorted(first, std::next(it), cmp)); } } 

请注意， insertion_sort已经处理的范围[first, it)sorting为其循环不变。 插入sorting也适用于正向迭代器。

细节省略 ：

• if (std::distance(first, last) <= 1) return;则可以使用早期testing来优化插入sortingif (std::distance(first, last) <= 1) return; （或者对于正向/双向迭代器： if (first == last || std::next(first) == last) return; ）和一个循环遍历间隔[std::next(first), last) ，因为第一个元素保证在位，不需要旋转。
• 对于双向迭代器 ，使用标准库的std::find_if_notalgorithm， 可以使用反向线性search来replace用于查找插入点的二进制search。

以下片段的四个实例 （ C ++ 14 ， C ++ 11 ， C ++ 98和Boost ， C ++ 98 ）：

 using RevIt = std::reverse_iterator<BiDirIt>; auto const insertion = std::find_if_not(RevIt(it), RevIt(first), [=](auto const& elem){ return cmp(*it, elem); } ).base(); 

• 对于随机input，这给出了O(N^2)比较，但是对于几乎分类的input，这改进为O(N)比较。 二进制search总是使用O(N log N)比较。
• 对于小的input范围，线性search的更好的内存位置（caching，预取）也可能支配二进制search（当然，应该testing这个）。

快速sorting

当仔细实施时， 快速sorting是健壮的，具有O(N log N)期望的复杂度，但是具有O(N^2)最差的复杂度，可以通过对抗select的input数据来触发。 当不需要稳定的sorting时，快速sorting是一个很好的通用sorting。

即使是最简单的版本，使用标准库的快速sorting也比其他经典的sortingalgorithm复杂得多。 下面的方法使用一些迭代器工具来定位input范围[first, last)的中间元素为pivot，然后使用两个调用std::partition （它们是O(N) ）来对input进行三路分区范围分别为小于，等于和大于所选枢轴的元素的分段。 最后，具有小于和大于枢轴的元素的两个外部分段被recursionsorting：

 template<class FwdIt, class Compare = std::less<>> void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { auto const N = std::distance(first, last); if (N <= 1) return; auto const pivot = *std::next(first, N / 2); auto const middle1 = std::partition(first, last, [=](auto const& elem){ return cmp(elem, pivot); }); auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ return !cmp(pivot, elem); }); quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp)); quick_sort(middle2, last, cmp); // assert(std::is_sorted(middle2, last, cmp)); } 

但是，快速sorting要得到正确和有效率是相当棘手的，因为上述每个步骤都必须仔细检查和优化生产级代码。 特别是对于O(N log N)复杂性，主轴必须产生一个input数据的平衡分区，这对于一个O(1)主轴来说是不能保证的，但是如果设置主轴作为input范围的O(N)中位数。

细节省略 ：

• 上述实现特别容易受到特殊input的影响，例如，对于“ pipe风琴 ”input1, 2, 3, ..., N/2, ... 3, 2, 1 （因为中间总是大于其他所有元素）。
• 从input范围中的随机select的元素中select3个枢轴来防止几乎分类的input，否则其复杂度将恶化到O(N^2) 。
• 对std::partition的两个调用所显示的3-way分区 （分隔小于，等于和大于pivot的元素）并不是最有效的O(N)algorithm来实现这个结果。
• 对于随机访问迭代器 ，通过使用std::nth_element(first, middle, last) 中间数据透视select ，然后recursion调用quick_sort(first, middle, cmp)和quick_sort(middle, last, cmp) 。
• 然而，这个保证是有代价的，因为std::nth_element的O(N)复杂度的常数因子可能比O(1)中值为3的O(1)复杂度更昂贵，后面跟着O(N)调用std::partition （这是一个caching友好的单向数据通过）。

合并sorting

如果使用O(N)额外空间是无关紧要的，那么合并sorting是一个很好的select：它是唯一稳定的 O(N log N)sortingalgorithm。

使用标准algorithm很容易实现：使用一些迭代器实用程序来定位input范围的中间[first, last) ，并将两个recursionsorting的段与std::inplace_merge ：

 template<class BiDirIt, class Compare = std::less<>> void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{}) { auto const N = std::distance(first, last); if (N <= 1) return; auto const middle = std::next(first, N / 2); merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp)); merge_sort(middle, last, cmp); // assert(std::is_sorted(middle, last, cmp)); std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp)); } 

合并sorting需要双向迭代器，瓶颈是std::inplace_merge 。 请注意，sorting链接列表时，合并sorting只需要O(log N)额外的空间（用于recursion）。 后一种algorithm是通过标准库中的std::list<T>::sort实现的。

堆sorting

堆sorting很容易实现，执行O(N log N)就地sorting，但不稳定。

第一个循环， O(N) “heapify”阶段，把数组放入堆的顺序。 第二个循环O(N log N ）“分类”阶段，反复提取最大值并恢复堆顺序。 标准库使这非常简单：

 template<class RandomIt, class Compare = std::less<>> void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{}) { lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp)); lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp)); } 

如果你认为使用std::make_heap和std::sort_heap是“作弊”的std::sort_heap ，你可以深入一层，并分别使用std::make_heap和std::sort_heap来编写这些函数：

 namespace lib { // NOTE: is O(N log N), not O(N) as std::make_heap template<class RandomIt, class Compare = std::less<>> void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{}) { for (auto it = first; it != last;) { std::push_heap(first, ++it, cmp); assert(std::is_heap(first, it, cmp)); } } template<class RandomIt, class Compare = std::less<>> void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{}) { for (auto it = last; it != first;) { std::pop_heap(first, it--, cmp); assert(std::is_heap(first, it, cmp)); } } } // namespace lib 

标准库指定push_heap和pop_heap为复杂度O(log N) 。 但是请注意，在[first, last)范围内的外部循环导致make_heap O(N log N)复杂度，而std::make_heap仅具有O(N)复杂度。 对于heap_sort的整体O(N log N)复杂性，这并不重要。

省略了详细信息 ： O(N)执行make_heap

testing

这里有四个Live示例 （ C ++ 14 ， C ++ 11 ， C ++ 98和Boost ， C ++ 98 ），在各种input（不意味着详尽或严格）上testing所有五种algorithm。 只需注意LOC中的巨大差异：C ++ 11 / C ++ 14需要大约130 LOC，C ++ 98和Boost 190（+ 50％）以及C ++ 98大于270（+ 100％）。

Answer 2

另一个小而优雅的代码审查最初发现 。 我认为这是值得分享的。

计数sorting

计数sorting是一个简单的整数sortingalgorithm，通常可以非常快速地提供sorting整数的值不会太远。 例如，如果需要对已知在0和100之间的一百万整数的集合进行sorting，则这可能是理想的。

要实现一个非常简单的计数sorting，可以同时使用有符号整数和无符号整数，需要查找集合中最小和最大的元素进行sorting; 他们的差异将会告诉要分配的计数数组的大小。 然后，第二次通过集合来计算每个元素的出现次数。 最后，我们将每个整数的所需数量回写回原始集合。

 template<typename ForwardIterator> void counting_sort(ForwardIterator first, ForwardIterator last) { if (first == last || std::next(first) == last) return; auto minmax = std::minmax_element(first, last); // avoid if possible. auto min = *minmax.first; auto max = *minmax.second; if (min == max) return; using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; std::vector<difference_type> counts(max - min + 1, 0); for (auto it = first ; it != last ; ++it) { ++counts[*it - min]; } for (auto count: counts) { first = std::fill_n(first, count, min++); } } 

虽然只有当整数的整数范围很小（通常不大于要分类的集合的大小）时，它才有用，但是使计数sorting更通用会使其最好的情况变得更慢。 如果范围不是很小，则可以使用另一种algorithm，如基数sorting ， ska_sort或spreadort 。

细节省略 ：

• 我们可以通过algorithm所接受的值范围的边界作为参数来彻底摆脱通过集合的第一个std::minmax_element传递。 当通过其他方式知道有用的小范围限制时，这将使algorithm更快。 （它不一定是确切的;传递一个0到100的常量要比通过一百万个元素的额外传递要好得多，以便发现真实的边界是1到95，即使是0到1000也是值得的;额外的元素被写入一次零并读取一次）。

• 在飞行中越来越多的counts是另一种避免单独第一遍的方法。 每增加一倍， counts大小就会增加，每个sorting元素的O（1）时间就会被分摊（参见散列表插入成本分析，以certificate指数增长是关键）。 在最后增加一个新的max容易与std::vector::resize添加新的归零元素。 dynamic更改min并在前面插入新的归零元素可以在生成向量后用std::copy_backward完成。 然后std::fill零新的元素。

• counts递增循环是一个直方图。 如果数据可能是高度重复的，并且分箱数量很小，则可能需要展开多个数组以减less存储/重装到同一分箱的序列化数据依赖性瓶颈。 这意味着在开始时更多地计数为零，并且更多地在最后循环，但是对于我们的例如数百万个0到100个数字的多数CPU来说应该是值得的，特别是如果input可能已经（部分地）sorting并且长时间运行相同的数字。

• 在上面的algorithm中，当每个元素具有相同的值（在这种情况下，集合被sorting）时，我们使用min == max检查来提前返回。 实际上，可以完全检查集合是否已经被sorting，同时发现集合的极端值，而不浪费额外的时间（如果第一遍仍然是内存瓶颈，则需要额外的更新min和max的工作）。 然而，在标准库中不存在这样的algorithm，编写一个algorithm比编写其余的计数sorting本身更乏味。 这是留给读者的一个练习。

• 由于该algorithm仅适用于整数值，因此可以使用静态断言来防止用户发生明显的types错误。 在某些情况下， std::enable_if_treplace失败可能是首选。

• 虽然现代的C ++很酷，但未来的C ++可能会更酷： 结构化的绑定和Ranges TS的某些部分会使algorithm更清晰。