如何在现代C ++中实现经典的排序算法？
来自C ++标准库的std::sort算法（和它的cousins std::partial_sort和std::nth_element ）在大多数实现中是一个更复杂和混合的更多基本排序算法的混合，比如选择排序，插入排序，快速排序，合并排序或堆排序。
这里和姊妹网站上存在很多问题，例如https://codereview.stackexchange.com/与错误，复杂性以及这些经典排序算法实现的其他方面有关。 大多数提供的实现都由原始循环组成，使用索引操作和具体类型，并且通常在正确性和效率方面不是微不足道的。
问题 ：如何使用现代C ++实现上述经典排序算法？
<algorithm>的标准库的算法构建块 auto模板别名，透明比较器和多态lambda表达式。 备注 ：
for -loop比与操作者的两个功能组合物更长的时间。 所以f(g(x)); 或f(x); g(x); f(x); g(x); 或f(x) + g(x); 不是原始循环，也不是下面的selection_sort和insertion_sort中的循环。 算法构建块
我们从组装标准库中的算法构建块开始：
#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_sorted算法仅适用于C ++ 11及更高版本。 对于C ++ 98，这可以通过std::adjacent_find和一个手写函数对象来实现。 Boost.Algorithm还提供了boost::algorithm::is_sorted作为替代。 std::is_heap算法仅适用于C ++ 11及更高版本。 语法好的东西
C ++ 14提供了形式为std::less<> 透明比较器 ，这些比较器在其参数上进行多态操作。 这避免了必须提供迭代器的类型。 这可以与C ++ 11的默认函数模板参数结合使用，以为排序算法创建单个重载 ，这些排序算法采用<作为比较以及具有用户定义的比较函数对象的排序算法。
template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});
在C ++ 11中，可以定义一个可重用的模板别名来提取迭代器的值类型，从而为排序算法的签名添加次要的混乱：
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>());
}
auto参数，这些参数可以像函数模板参数一样推导出来）方便地包装用户定义的比较器。 value_type_t 。 std::bind1st / std::bind2nd / std::not1语法类型。 boost::bind和_1 / _2占位符语法改进了这一点。 std::find_if_not ，而C ++ 98需要std::find_if和函数对象周围的std::not1 。 C ++风格
目前还没有普遍接受的C ++ 14风格。 更糟糕的是，我密切关注Scott Meyers的Effective Modern C ++草案和Herb Sutter 改进后的GotW 。 我使用以下风格建议：
()和{} ”并始终选择使用braced-initialization {}而不使用旧的带括号的初始化() （以便旁路通用代码中所有最棘手的分析问题）。 typedef节省时间并增加一致性。 for (auto it = first; it != last; ++it)模式，以便对已排序的子范围进行循环不变量检查。 在生产代码中，循环内某处使用while (first != last)和++first会稍微好一些。 选择排序
选择排序不能以任何方式适应数据，所以它的运行时间始终是O(N^2) 。 然而，选择种类具有最小化交换次数的性质 。 在交换项目成本高的应用中，选择排序非常好可能是选择的算法。
要使用标准库来实现它，请重复使用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)排序为其循环不变量。 与std::sort的随机访问迭代器相比，最小需求是前向迭代器。
细节省略 ：
if (std::distance(first, last) <= 1) return;则可以使用早期测试来优化选择排序if (std::distance(first, last) <= 1) return; （或者对于前向/双向迭代器： if (first == last || std::next(first) == last) return; ）。 [first, std::prev(last)) ，因为最后一个元素保证是最小的剩余元素，不需要交换。 插入排序
虽然它是具有O(N^2)最差情况时间的基本排序算法之一，但插入排序是当数据几乎排序（因为它是自适应的 ）或问题规模很小（因为它具有低开销）。 出于这些原因，并且因为它也是稳定的 ，所以插入排序经常被用作递归基本情况（当问题规模较小时）用于较高开销的分而治之排序算法，例如合并排序或快速排序。
要使用标准库实现insertion_sort ，请重复使用std::upper_bound来查找当前元素需要去的位置，并使用std::rotate在输入范围中向上移动其余元素：
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)排序为其循环不变量。 插入排序也适用于前向迭代器。
细节省略 ：
if (std::distance(first, last) <= 1) return;插入排序可以通过早期测试进行优化if (std::distance(first, last) <= 1) return; （或对于正向/双向迭代器： if (first == last || std::next(first) == last) return; ）和一个循环遍历间隔[std::next(first), last) ，因为第一个元素保证到位并且不需要旋转。 std::find_if_not算法可以用反向线性搜索来替换用于查找插入点的二进制搜索。 四个Live示例 （ 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();
O(N^2)比较，但是对于几乎分类的输入，这改进为O(N)比较。 二进制搜索始终使用O(N log N)比较。 快速排序
当仔细实施时， 快速排序是稳健的，并且具有O(N log N)预期的复杂度，但是O(N^2)最坏情况的复杂度可以通过对抗选择的输入数据来触发。 当不需要稳定的排序时，快速排序是非常好的通用排序。
即使对于最简单的版本，使用标准库的快速排序也比其他经典的排序算法复杂得多。 下面的方法使用一些迭代器实用程序来定位输入范围[first, last)的中间元素作为支点，然后使用两个调用std::partition （它们是O(N) ）来对输入进行三路分区范围分别分成小于，等于和大于所选枢轴的元素段。 最后，具有小于和大于枢轴的元素的两个外部分段递归排序：
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));
}
但是，快速排序要得到正确和高效，相当棘手，因为必须仔细检查每个上述步骤并针对生产级代码进行优化。 特别是，对于O(N log N)复杂度，主轴必须产生输入数据的平衡分区，这通常不能保证O(1)主轴，但如果设置主轴作为输入范围的O(N)中位数。
细节省略 ：
1, 2, 3, ..., N/2, ... 3, 2, 1 O(N^2)具有O(N^2)因为中间总是大于其他所有元素）。 O(N^2) 。 std::partition的两次调用所显示的3-way分区 （小于，等于和大于pivot的分隔元素）不是实现此结果的最高效的O(N)算法。 O(N log N)复杂性可以通过中值选择枢轴使用来实现std::nth_element(first, middle, last) ，接着递归调用quick_sort(first, middle, cmp)和quick_sort(middle, last, cmp) 。 std::nth_element的O(N)复杂度的常数因子比O(1)中值为3的中心的O(1)复杂度更昂贵，后面跟着O(N)调用std::partition （这是一个缓存友好的单向数据传输）。 合并排序
如果使用O(N)额外空间是无关紧要的，那么合并排序是一个很好的选择：它是唯一稳定的 O(N log N)排序算法。
使用标准算法很容易实现：使用一些迭代器实用程序来定位输入范围的中间[first, last) ，并将两个递归排序的段与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));
}
合并排序需要双向迭代器，瓶颈是std::inplace_merge 。 请注意，排序链接列表时，合并排序只需要O(log N)额外空间（用于递归）。 后一种算法由标准库中的std::list<T>::sort 。
堆排序
堆排序很容易实现，执行O(N log N)就地排序，但不稳定。
第一个循环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::push_heap和std::pop_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
测试
这里有四个Live示例 （ C ++ 14 ， C ++ 11 ， C ++ 98和Boost ， C ++ 98 ），它们在各种输入（不意味着详尽或严格）上测试所有五种算法。 只需注意LOC中的巨大差异：C ++ 11 / C ++ 14需要大约130 LOC，C ++ 98和Boost 190（+ 50％）以及C ++ 98大于270（+ 100％）。
最初在代码审查中发现的另一个小而优雅的代码。 我认为这是值得分享的。
计数排序
虽然它是相当专业化的，但计数排序是一种简单的整数排序算法，并且通常可以非常快速地提供要整理的整数值相距不太远。 例如，如果需要对已知介于0和100之间的一百万整数的集合进行排序，则这可能是理想的。
为了实现一个非常简单的计数排序，可以同时使用有符号整数和无符号整数，需要查找集合中最小和最大的元素进行排序; 他们的差异将会显示要分配的计数数组的大小。 然后，第二次通过收集来完成每个元素的出现次数。 最后，我们将每个整数的所需数量回写回原始集合。
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++);
}
}
虽然只有当整理的整数范围已知很小（通常不大于要排序的集合的大小）时，它才有用，但使计数排序更通用会使它在最佳情况下变得更慢。 如果范围不是很小，可以使用另一种算法，如基数排序，ska_sort或spreadort。
细节省略 ：
我们可以通过算法接受的值范围的边界作为参数，完全摆脱集合中的第一个std::minmax_element传递。 当通过其他方法知道有用的小范围限制时，这将使算法更快。 （它并不一定是确切的;传递一个0到100的常量仍然好于多于一百万个元素的额外传递，以发现真正的边界是1到95.即使0到1000也是值得的;额外的元素用零写入一次并读取一次）。
动态增加counts是另一种避免单独第一遍的方法。 每增加一个counts大小加倍，每个排序元素的O（1）时间就会分摊（关于证明指数增长是关键的参见哈希表插入成本分析）。 在结束了一个新的成长max是容易std::vector::resize ，以增加新的归零元素。 动态更改min并在前面插入新的归零元素可以在生成向量后用std::copy_backward完成。 然后std::fill为零的新元素。
counts增量循环是一个直方图。 如果数据可能是高度重复的，并且分箱数量很小，则可能需要展开多个阵列以减少存储/重新加载到同一分箱的序列化数据依赖性瓶颈。 这意味着在开始时更多地计数为零，并且在最后循环的次数更多，但是对于我们的例子中的数百万个0到100个数字，在大多数CPU上应该是值得的，特别是如果输入可能已经（部分）排序并且长期运行的数量相同。
在上面的算法中，当每个元素具有相同的值时（在这种情况下，集合被排序），我们使用min == max检查来提前返回。 实际上，可以完全检查集合是否已被排序，同时发现集合的极端值而不浪费额外时间（如果第一次传递仍然是存储器瓶颈，则需要额外的工作来更新最小值和最大值）。 然而，这种算法在标准库中不存在，编写一个算法比编写其他计数排序本身更乏味。 它留给读者作为练习。
由于该算法仅适用于整数值，因此可以使用静态断言来防止用户发生明显的类型错误。 在某些情况下， std::enable_if_t替换失败可能是首选。
虽然现代C ++很酷，但未来的C ++可能会更酷：结构化绑定和Ranges TS的某些部分会使算法更清晰。
上一篇: How to implement classic sorting algorithms in modern C++?