如何在现代c++中实现经典的排序算法?

c++标准库中的std::sort算法(及其表兄弟std::partial_sort和std::nth_element)在大多数实现中都是一种更基本的排序算法的复杂和混合融合，例如选择排序、插入排序、快速排序、归并排序或堆排序。

这里和姐妹网站(如https://codereview.stackexchange.com/)上有许多与这些经典排序算法实现的错误、复杂性和其他方面有关的问题。大多数提供的实现都由原始循环组成，使用索引操作和具体类型，并且在正确性和效率方面分析起来通常不是简单的。

问题:如何使用现代c++实现上面提到的经典排序算法?

  • 没有原始循环，但是结合了来自<algorithm>的标准库算法构建块
  • 迭代器接口和使用模板代替索引操作和具体类型
  • c++ 14风格，包括完整的标准库，以及语法降噪器，如auto、模板别名、透明比较器和多态lambda。

笔记:

  • 有关排序算法实现的进一步参考，请参阅维基百科， 罗塞塔的代码或http://www.sorting-algorithms.com/
  • 根据Sean Parent的惯例 .(幻灯片39)，原始循环是一个__abc0 -循环，比两个带有运算符的函数的组合还要长。所以f(g(x));或f(x); g(x);或f(x) + g(x);不是原始循环，下面的selection_sort和insertion_sort中的循环也不是原始循环。
  • 我遵循Scott Meyers的术语，将当前的c++ 1y表示为c++ 14，并将c++ 98和c++ 03都表示为c++ 98，所以不要因此而责怪我。
  • 正如@Mehrdad在评论中所建议的那样，我在回答的最后提供了四个实现作为现场示例:c++ 14, c++ 11, c++ 98和Boost和c++ 98。
  • 答案本身只在c++ 14中给出。在相关的地方，我指出了不同语言版本的语法和库差异。
34645 次浏览
小开
最佳答案

算法构建块

我们从组装标准库的算法构建块开始:

#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有替代品。范围为boost::begin() / boost::end()，并从Boost。boost::next()中的实用程序。
  • std::is_sorted算法仅适用于c++ 11及以上版本。对于c++ 98，这可以通过std::adjacent_find和一个手写的函数对象来实现。提振。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>());
}
  • 另一个语法细节是c++ 14通过多态λ方便地包装用户定义的比较器(使用auto形参，这些形参像函数模板实参一样被推导出来)。
  • c++ 11只有单形lambda，这需要使用上面的模板别名value_type_t。
  • 在c++ 98中，你要么需要编写一个独立的函数对象，要么使用冗长的std::bind1st / std::bind2nd / std::not1类型的语法。
  • 提振。Bind通过boost::bind和_1 / _2占位符语法改进了这一点。
  • c++ 11及以上版本也有std::find_if_not，而c++ 98需要在函数对象周围加上std::not1的std::find_if。

c++风格

目前还没有普遍接受的c++ 14风格。不管是好是坏，我密切关注Scott Meyers的draft Effective Modern c++ 和Herb Sutter的< >强调整GotW < / >强。我推荐以下风格:

  • Herb Sutter的"Almost Always Auto" .和Scott Meyers的"Prefer auto to specific type declarations" .建议，其简洁性是无与伦比的，尽管其清晰度有时是< >强有争议的< / >强。
  • Scott Meyers的 "创建对象时区分__ABC0和{}，并始终选择带括号的初始化{}，而不是旧的带括号的初始化()(为了避开泛型代码中所有最恼人的解析问题)。
  • 斯科特·迈尔斯的"Prefer alias declarations to 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)中位数，则可以保证。

细节省略:

  • 上面的实现特别容易受到特殊输入的影响，例如，对于“风琴管”输入1, 2, 3, ..., N/2, ... 3, 2, 1，它具有O(N^2)复杂度(因为中间元素总是比所有其他元素都大)。
  • < >强median-of-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)。
  • 然而，这种保证是有代价的，因为std::nth_element的O(N)复杂度这一常量因素可能比一个3中位数枢轴的O(N)调用std::partition(这是一个缓存友好的单次数据转发)的O(1)复杂度更昂贵。

归并排序

如果不考虑使用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)复杂性来说，这并不重要。

细节省略: __ABC0实现make_heap

测试

这里有四个生活的例子 (< >强c++ 14 < / >强， < >强c++ 11 < / >强， c++ 98和Boost， < >强c++ 98 < / >强)在各种输入上测试所有五种算法(并不意味着详尽或严格)。只需注意LOC的巨大差异:c++ 11/ c++ 14需要大约130个LOC, c++ 98和Boost需要190个LOC(+50%)，而c++ 98需要270多个LOC(+100%)。

小开

另一个小而相当优雅的最初发现于代码审查。我觉得值得分享。

计数排序

计数排序是一个简单的整数排序算法，如果要排序的整数的值相距不是太远，它通常可以非常快。例如，如果需要对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或spreadsort。

细节省略:

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

  • 动态递增counts是避免单独的第一次传递的另一种方法。每次counts的大小增加一倍，每个排序的元素就会平摊O(1)时间(参见哈希表插入成本分析，以证明指数增长是关键)。使用std::vector::resize可以很容易地在新max的末尾增加新的零元素。 动态更改min并在前面插入新的归零元素可以在增加vector后使用std::copy_backward完成。然后std::fill将新元素归零

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

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

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

  • 虽然现代c++很酷，但未来的c++可能会更酷:结构化绑定和Ranges TS将使算法更加清晰。

小开

Visual Studio 2015年之前版本使用链表的自下而上的归并排序,但换了一个较有效的(由于扫描列表将通过std::下一个)自顶向下归并排序的链表的时候改变处理没有默认分配器使用基于迭代器的算法,也提供异常安全如果比较(用户定义)抛出一个异常(旧版本,比较例外将失去在内部数组列表的一部分)。当这是第一次质疑，我认为有一些问题，实现一个基于迭代器自下而上归并排序链表，但后来确定没有问题。唯一的“聪明”;我的部分实现是使用std::list::end()(一个常量)来指示一个空的子列表(因为迭代器不能为空)。链接到我的回答，显示std::list::sort()的独立和替换代码:

https://stackoverflow.com/a/40629882/3282056 < a href = " https://stackoverflow.com/a/40629882/3282056 " > < / >


提交答案