如何在现代 C++ 中实现经典排序算法？

算法构建块

我们首先从标准库中组装算法构建块：

#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.Range 的替代品，在 boost::next() 中有来自 Boost.Utility 的替代品。

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<> 形式的 transparent comparators，它们多态地作用于它们的参数。这避免了必须提供迭代器的类型。这可以与 C++11 的 default function template arguments 结合使用，为将 < 作为比较和具有用户定义的比较函数对象的排序算法创建单个重载。

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

在 C++11 中，可以定义一个可重用的 template alias 来提取迭代器的值类型，这会为排序算法的签名添加轻微的混乱：

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 有助于通过多态 lambda 包装用户定义的比较器（使用自动参数，如函数模板参数一样推导出来）。

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::find_if 和 std::not1 围绕函数对象。

C++ 风格

目前还没有普遍接受的 C++14 风格。无论好坏，我都密切关注 Scott Meyers 的 draft Effective Modern C++ 和 Herb Sutter 的 revamped GotW。我使用以下样式建议：

Herb Sutter 的“Almost Always Auto”和 Scott Meyers 的“Prefer auto to specific type declarations”建议的简洁性是无与伦比的，尽管其清晰度有时存在争议。

Scott Meyers 的“在创建对象时区分 () 和 {}”，并始终选择大括号初始化 {} 而不是旧的带括号的初始化 ()（为了回避通用代码中所有最棘手的解析问题）。

Scott Meyers 的“Prefer alias declarations to typedefs”。对于模板来说，无论如何这是必须的，并且在任何地方都使用它而不是 typedef 可以节省时间并增加一致性。

我在某些地方使用了 for (auto it = first; it != last; ++it) 模式，以允许对已排序的子范围进行循环不变检查。在生产代码中，在循环内的某处使用 while (first != last) 和 ++first 可能会稍微好一些。

选择排序

Selection sort 不会以任何方式适应数据，因此其运行时始终为 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 是首选算法尺寸很小（因为它的开销很低）。由于这些原因，并且因为它也是稳定，插入排序通常用作递归基本情况（当问题规模较小时），用于更高开销的分治排序算法，例如合并排序或快速排序。

要使用标准库实现 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 and 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) 比较。

对于较小的输入范围，线性搜索的更好的内存局部性（缓存、预取）也可能主导二分搜索（当然，应该对此进行测试）。

快速排序

如果仔细实施，quick sort 是稳健的，并且具有 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); // 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) 枢轴，但如果将枢轴设置为 {3 } 输入范围的中位数。

细节省略：

上述实现特别容易受到特殊输入的影响，例如，对于“风琴管”输入 1, 2, 3, ..., N/2, ... 3, 2, 1 (因为中间总是大于所有其他元素）。

从输入范围中随机选择的元素中选择 3 的中值可以防止几乎排序的输入，否则复杂性会恶化到 O(N^2)。

如对 std::partition 的两次调用所示，三向分区（分隔小于、等于和大于枢轴的元素）并不是实现此结果的最有效的 O(N) 算法。

对于随机访问迭代器，可以通过使用 std::nth_element(first, middle, last) 的中值主元选择，然后递归调用 quick_sort(first, middle, cmp) 和 quick_sort(中间，最后，cmp）。

然而，这种保证是有代价的，因为 std::nth_element 的 O(N) 复杂度的常数因子可能比中位数为 3 的枢轴后面跟着 O 的 O(1) 复杂度的常数因子更昂贵(N) 调用 std::partition （这是对数据的缓存友好的单次前向传递）。

合并排序

如果不考虑使用 O(N) 额外空间，那么 merge sort 是一个很好的选择：它是唯一的稳定 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 实现。

堆排序

Heap 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) implementation of make_heap

测试

以下是四个实时示例（C++14、C++11、C++98 and Boost、C++98）在各种输入上测试所有五种算法（并非详尽或严格）。请注意 LOC 的巨大差异：C++11/C++14 需要大约 130 LOC，C++98 和 Boost 190 (+50%) 和 C++98 超过 270 (+100%)。

---

另一个小而优雅的originally found on code review。我觉得值得分享。

计数排序

虽然它相当专业，但 counting sort 是一种简单的整数排序算法，如果要排序的整数的值相距不太远，通常可以非常快。例如，如果需要对已知在 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++);
    }
}

虽然它仅在已知要排序的整数范围很小（通常不大于要排序的集合的大小）时才有用，但使计数排序更通用会使其在最佳情况下变慢。如果不知道该范围很小，则可以使用另一种算法，例如 radix sort、ska_sort 或 spreadsort。

细节省略：

我们本可以将算法接受的值范围的边界作为参数传递，以完全摆脱第一个 std::minmax_element 通过集合的传递。当通过其他方式知道有用的小范围限制时，这将使算法更快。 （不一定要精确；传递一个常数 0 到 100 仍然比额外传递一百万个元素要好得多，以找出真正的界限是 1 到 95。即使是 0 到 1000 也是值得的；额外的元素用零写入一次并读取一次）。

快速增加计数是避免单独的第一次通过的另一种方法。每次必须增长时将计数大小加倍会为每个排序元素提供分摊的 O(1) 时间（请参阅哈希表插入成本分析以证明指数增长是关键）。使用 std::vector::resize 添加新的零元素很容易在最后增长新的最大值。在增加向量后，可以使用 std::copy_backward 动态更改 min 并在前面插入新的零元素。然后 std::fill 将新元素归零。

计数增量循环是一个直方图。如果数据可能是高度重复的，并且 bin 的数量很少，则值得展开多个数组以减少存储/重新加载到同一 bin 的序列化数据依赖性瓶颈。这意味着在开始时更多的计数为零，并且在结束时循环更多，但是对于我们的数百万个 0 到 100 数字的示例，在大多数 CPU 上应该是值得的，特别是如果输入可能已经（部分）排序并且有相同数量的长跑。

在上面的算法中，我们使用 min == max 检查在每个元素具有相同值时提前返回（在这种情况下，集合已排序）。实际上，可以在不浪费额外时间的情况下完全检查集合是否已经排序，同时查找集合的极值（如果第一次通过更新最小值和最大值的额外工作仍然是内存瓶颈）。然而，标准库中不存在这样的算法，编写一个比编写计数排序本身的其余部分更乏味。它留给读者作为练习。

由于该算法仅适用于整数值，因此可以使用静态断言来防止用户犯明显的类型错误。在某些情况下，可能首选使用 std::enable_if_t 的替换失败。

虽然现代 C++ 很酷，但未来的 C++ 可能会更酷：结构化绑定和 Ranges TS 的某些部分将使算法更加简洁。

---