如何在现代 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

• 迭代器工具（如 non-member / 以及 with）仅在 C++11 及更高版本中可用。对于 C++98，需要自己编写这些内容。/ 中有 Boost.Range 的替代品，以及 中的 Boost.Utility 的替代品。std::begin()std::end()std::next()boost::begin()boost::end()boost::next()
• 该算法仅适用于 C++11 及更高版本。对于 C++98，这可以通过手写函数对象来实现。Boost.Algorithm 还提供了 a 作为替代。std::is_sortedstd::adjacent_findboost::algorithm::is_sorted
• 该算法仅适用于 C++11 及更高版本。std::is_heap

句法好东西

C++14 提供了形式的透明比较器，这些比较器对其参数进行多态作用。这样就不必提供迭代器的类型。这可以与 C++11 的默认函数模板参数结合使用，以创建单个重载，用于排序作为比较的算法和具有用户定义的比较函数对象的算法。std::less<><

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>());
}

• 另一个语法细节是 C++14 有助于通过多态 lambda（具有像函数模板参数一样推导的参数）包装用户定义的比较器。auto
• C++11 只有单态 lambda，需要使用上述模板别名。value_type_t
• 在 C++98 中，要么需要编写一个独立的函数对象，要么求助于冗长的 / / 语法类型。std::bind1ststd::bind2ndstd::not1
• Boost.Bind 使用 and / 占位符语法改进了这一点。boost::bind_1_2
• C++ 及更高版本也有 ，而 C++98 需要围绕一个函数对象。std::find_if_notstd::find_ifstd::not1

C++ 风格

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

• Herb Sutter 的“Almost Always Auto”和 Scott Meyers 的“Prefer auto 而不是 specific type declarations”的建议，其简洁性无与伦比，尽管其清晰度有时会引起争议。
• Scott Meyers 的“创建对象时区分 （） 和 {}”，并始终如一地选择支撑初始化而不是旧的括号初始化（以回避泛型代码中所有最棘手的解析问题）。{}()
• Scott Meyers 的“Prefer alias declarations than typedefs”。对于模板来说，无论如何，这是必须的，并且在任何地方使用它，而不是节省时间并增加一致性。typedef
• 我在某些地方使用一种模式，以便对已经排序的子范围进行循环不变检查。在生产代码中，在循环中的某个位置使用 and 可能会稍微好一些。for (auto it = first; it != last; ++it)while (first != last)++first

选择排序

选择排序不会以任何方式适应数据，因此其运行时始终为 。但是，选择排序具有最小化交换次数的属性。在交换项目成本较高的应用程序中，选择排序很可能是首选算法。O(N²)

要使用标准库实现它，请重复使用 以查找剩余的最小元素，并将其交换到位：std::min_elementiter_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²)

要使用标准库实现，请重复使用 to 查找当前元素需要去的位置，并使用 在输入范围内向上移动剩余元素：insertion_sortstd::upper_boundstd::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::partitionO(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)

细节省略：

• 上述实现特别容易受到特殊输入的影响，例如，它对“管风琴”输入具有复杂性（因为中间总是比所有其他元素都大）。O(N^2)1, 2, 3, ..., N/2, ... 3, 2, 1
• 从输入范围中随机选择的元素中选择中位数的 3 个枢轴可防止几乎排序的输入，否则其复杂性会恶化到 。O(N^2)
• 三次调用 to 所示的 3 向分区（分离小于、等于和大于枢轴的元素）并不是实现此结果的最有效算法。std::partitionO(N)
• 对于随机访问迭代器，可以通过使用 的中值枢轴选择来实现有保证的复杂性，然后对 和 进行递归调用。O(N log N)std::nth_element(first, middle, last)quick_sort(first, middle, cmp)quick_sort(middle, last, cmp)
• 然而，这种保证是有代价的，因为复杂性的恒定因素可能比中位数为 3 的枢轴后跟调用的复杂性（这是对数据的缓存友好的单次前向传递）的复杂性更昂贵。O(N)std::nth_elementO(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_mergeO(log N)std::list<T>::sort

堆排序

堆排序易于实现，执行就地排序，但不稳定。O(N log N)

第一个循环，即“堆化”阶段，将数组按堆顺序排列。第二个循环，即 ） “sortdown” 阶段，重复提取最大值并恢复堆顺序。标准库使这一点变得非常简单：O(N)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));
}

如果您认为使用 and 是“作弊”，您可以更深入地使用和 分别编写这些函数：std::make_heapstd::sort_heapstd::push_heapstd::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_heappop_heapO(log N)[first, last)O(N log N)make_heapstd::make_heapO(N)O(N log N)heap_sort

省略细节：O（N） 实现 make_heap

测试

这里有四个实时示例（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 之间的 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或扩展排序。

细节省略：

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

• 即时种植是避免单独通过的另一种方法。每次必须增长时将大小加倍，每个排序元素的摊销时间为 O（1）（请参阅哈希表插入成本分析，以证明指数增长是关键）。通过添加新的零元素，很容易在最后为新的元素增长。 在增加矢量后，可以即时更改并在前面插入新的归零元素。然后将新元素归零。countscountsmaxstd::vector::resizeminstd::copy_backwardstd::fill

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

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

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

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