算法构建模块
我们首先从标准库中组装算法构建模块：
#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.Range提供了替代品boost::begin() / boost::end()，而Boost.Utility提供了boost::next()。
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);
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通过多态lambda（带有类似函数模板参数的
auto参数）简化了用户定义比较器的封装。
- C++11只有单态lambda，需要使用上面的模板别名
value_type_t。
- 在C++98中，需要编写独立的函数对象或者采用冗长的
std::bind1st/std::bind2nd/std::not1类型的语法。
- Boost.Bind通过
boost::bind和_1/_2占位符语法改进了这一点。
- C++11及以上版本还具有
std::find_if_not，而C++98需要将函数对象放在std::not1中的std::find_if。
C++风格
目前还没有被广泛接受的C++14风格。无论好坏，我紧密地遵循Scott Meyers的《Effective Modern C++》草案和Herb Sutter的改版GotW。我使用以下样式建议：
选择排序
选择排序 不会根据数据进行任何适应，因此其运行时间始终为 O(N²)。然而，选择排序具有“最小化交换次数”的特性。在交换项成本很高的应用中，选择排序可能是最佳的算法选择。
使用标准库实现它时，重复使用 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 (first == last || std::next(first) == last) return;）来优化选择排序。
- 对于双向迭代器，上述测试可以与在区间
[first，std::prev(last))上的循环结合使用，因为最后一个元素保证是剩余元素中最小的，并且不需要交换。
插入排序
尽管插入排序是一种基本的排序算法，其最坏情况时间复杂度为
O(N²)，但当数据几乎有序（因为它是自适应的）或问题规模较小（因为它的开销较低）时，
插入排序是首选算法。出于这些原因，并且因为它也是
稳定的，插入排序通常被用作高开销的分治排序算法（如归并排序或快速排序）的递归基本情形（当问题规模很小时）。
要使用标准库实现
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 (first == last || std::next(first) == last) return;），并循环遍历区间
[std::next(first), last)，因为第一个元素保证已经就位，不需要旋转。
对于
双向迭代器，可以使用标准库的
std::find_if_not 算法替换二分查找来查找插入点的位置，而使用
反向线性查找。
以下是四个关于以下代码片段的实时示例 (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²）次比较，但对于几乎排序的输入，这将改善为O（N）次比较。二分搜索始终使用O（N log N）次比较。
- 对于小的输入范围，线性搜索更好的内存局部性（缓存、预取）可能也会支配二分搜索（当然应该进行测试）。
快速排序
仔细实现时，快速排序是强大且具有O（N log N）预期复杂度的，但最坏情况下的复杂度为O（N²），可以通过对手选择的输入数据来触发。当不需要稳定排序时，快速排序是一种优秀的通用排序方法。
即使对于最简单的版本，使用标准库实现快速排序比其他经典排序算法更加复杂。下面的方法使用了一些迭代器工具来找到输入范围[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);
quick_sort(middle2, last, cmp);
}
然而，快速排序相当棘手，需要仔细检查和优化每个步骤，以使其正确且高效。特别是对于O(N log N)复杂度，必须确保枢轴将输入数据分成平衡的分区，这在一般情况下无法保证使用O(1)枢轴，但如果将枢轴设置为输入范围的O(N)中位数，则可以保证。
细节已省略：
上述实现特别容易受到特殊输入的攻击，例如对于“organ pipe”输入1、2、3、…、N/2、…3、2、1，其复杂度为O（N^2）（因为中间元素始终大于所有其他元素）。从随机选择的元素中
选取,
中位数的枢轴选择可防范近乎排序的输入，否则其复杂度会恶化到O(N^2)。如两次调用std::partition所示，
三路分区（将小于、等于和大于枢轴的元素分开）不是实现此结果的最有效算法O（N）。对于随机访问迭代器,通过使用std::nth_element(first, middle, last)选择中位数枢轴，然后递归调用quick_sort(first, middle, cmp)和quick_sort(middle, last, cmp)，可以保证O（NlogN）的复杂度。然而，这种保证是有代价的，因为std::nth_element的O（N）复杂度的常数因子可能比中位数枢轴的O（1）复杂度加上单向遍历数据的缓存友好的std::partition的O（N）调用更昂贵。
归并排序
如果不考虑使用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);
merge_sort(middle, last, cmp);
std::inplace_merge(first, middle, last, cmp);
}
归并排序需要双向迭代器，瓶颈在于std::inplace_merge。请注意，在对链表进行排序时，归并排序仅需要额外的O(log N)空间（用于递归）。后一种算法由标准库中的std::list<T>::sort实现。
堆排序
堆排序易于实现，执行O(N log N)原地排序，但不稳定。
第一个循环，O(N)的“heapify”阶段，将数组放入堆顺序。第二个循环，O(N log N)的“sortdown”阶段，重复提取最大值并恢复堆顺序。标准库使这变得非常简单：
template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
lib::make_heap(first, last, cmp);
lib::sort_heap(first, last, cmp);
}
如果您认为使用std::make_heap和std::sort_heap是“作弊”的话，您可以再深入一层，分别使用std::push_heap和std::pop_heap编写这些函数：
namespace lib {
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));
}
}
}
标准库将
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)复杂度并不重要。
细节省略：
make_heap的O(N)实现
测试
这里有四个实时示例(C++14, C++11, C++98和Boost, C++98)，测试了所有五种算法在各种输入上的表现（不旨在全面或严格）。请注意代码行数方面的巨大差异：C++11 / C++14 需要约130行代码，C++98和Boost需要190行代码（增加了50%），而C++98则需要超过270行代码（增加了100%）。
