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

如何在现代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()以及with）std::next()仅从C版本开始可用11及以后。对于C98，需要自己写这些。有替代品从Boost.Range的boost::begin()/ boost::end()，并从Boost.Utility中boost::next()。
• 该std::is_sorted算法仅适用于C11及以后。对于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 implementationtemplate<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，需要使用上述模板

  alias value_type_t

  。
  在

  C ++ 98

  ，一个或者需要编写一个独立的功能对象或诉诸冗长

  std::bind1st/ std::bind2nd/ std::not1

  类型语法。

• Boost.Bind

  使用

  boost::bind

  和

  _1/ _2

  占位符语法对此进行了改进。
• C11及更高版本也有

  std::find_if_not

  ，而C98需要

  std::find_if

  带有

  std::not1

  一个功能对象。

C++ Style

目前尚无普遍接受的C 14样式。不管是好是坏，我都
密切关注Scott Meyers的草案有效的现代
C
和Herb Sutter 修改后的GotW。我使用
以下样式建议：

赫伯·萨特（Herb Sutter）的“几乎总是自动的”和斯科特·迈耶斯（Scott Meyers）的“首选自动使用特定类型的声明”的建议，尽管有时它的清晰度有时会引起争议，但其简洁性并没有超越。
斯科特·迈耶斯（Scott Meyers）的“区分()和{}创建对象时”，始终选择支撑初始化{}而不是旧的带括号的初始化()（以避开通用代码中所有最烦人的解析问题）。
斯科特·迈耶斯（Scott Meyers）的“首选别名声明而不是typedefs”。对于模板而言，无论如何都是必须的，并且在各处使用它而不是typedef节省时间和增加一致性。
我for (auto it = first; it != last; it)在某些地方使用了模式，以允许对已经排序的子范围进行循环不变检查。在生产代码中，在循环内使用while (first != last)和first可能会更好。

选择排序

选择排序不会
以任何方式适应数据，因此其运行时间始终为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); // 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)。
  如两次调用所示，三向分割（分隔小于，等于和大于枢轴的元素）std::partition并不是O(N)实现此结果的最有效算法。
  对于随机访问迭代器，O(N log N)可以通过使用中位枢纽选择std::nth_element(first, middle, last)，然后递归调用quick_sort(first, middle, cmp)和来实现保证的复杂性quick_sort(middle, last, cmp)。
  但是，此保证要付出一定的代价，因为的O(N)复杂度的恒定因素std::nth_element可能比O(1)3位中值枢纽点和随后的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)“堆”阶段，将数组置于堆顺序。在第二循环中，O(NlogN）“sortdown”阶段，反复提取最大和还原堆顺序。标准库使这一过程变得非常
简单：

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

In case you consider it “cheating” to use

std::make_heap

and

std::sort_heap

, you can go one level deeper and write those functions
yourself in terms of

std::push_heap

and

std::pop_heap

, respectively:

namespace lib {// NOTE: is O(N log N), not O(N) as std::make_heaptemplate<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)

导致的

O(N log N)

复杂性

make_heap

，而

std::make_heap

仅具有

O(N)

复杂性。对于整体

O(N log N)

复杂性而言，

heap_sort

这无关紧要。

测试中

这是四个实时示例（C 14，C 11，C 98和Boost，C 98），它们在各种 输入上测试所有五种算法（并非详尽无遗或严格）。只需注意 LOC 的巨大差异即可：C

11 /摄氏度14需要大约130 LOC，C98和Boost 190（+ 50％）和C98个超过270个（+ 100％）。