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


Answers

最初在代码审查中发现的另一个小而优雅的代码 。 我认为这是值得分享的。

计数排序

虽然它是相当专业化的,但计数排序是一种简单的整数排序算法,并且通常可以非常快速地提供要整理的整数值相距不太远。 例如,如果需要对已知介于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_sortspreadsort

细节省略

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

  • 动态增加counts是另一种避免单独第一遍的方法。 每增加一个counts大小加倍,每个排序元素的O(1)时间就会分摊(关于证明指数增长是关键的参见哈希表插入成本分析)。 使用std::vector::resize来添加新的零点元素非常容易。 动态更改min并在前面插入新的归零元素可以在生成向量后用std::copy_backward完成。 然后std::fill为零的新元素。

  • counts增量循环是一个直方图。 如果数据可能是高度重复的,并且分箱数量很小,则可能需要展开多个阵列以减少存储/重新加载到同一分箱的序列化数据依赖性瓶颈。 这意味着在开始时更多地计数为零,并且在最后循环的次数更多,但是对于我们的例子中的数百万个0到100个数字,在大多数CPU上应该是值得的,特别是如果输入可能已经(部分)排序并且长期运行的数量相同。

  • 在上面的算法中,当每个元素具有相同的值时(在这种情况下,集合被排序),我们使用min == max检查来提前返回。 实际上,可以完全检查集合是否已被排序,同时发现集合的极端值而不浪费额外时间(如果第一次传递仍然是存储器瓶颈,则需要额外的工作来更新最小值和最大值)。 然而,这种算法在标准库中不存在,编写一个算法比编写其他计数排序本身更乏味。 它留给读者作为练习。

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

  • 虽然现代C ++很酷,但未来的C ++可能会更酷: 结构化绑定Ranges TS的某些部分会使算法更清晰。

Question

来自C ++标准库的std::sort算法(和它的cousins std::partial_sortstd::nth_element )在大多数实现中是一个更复杂和混合的更多基本排序算法的混合 ,比如选择排序,插入排序,快速排序,合并排序或堆排序。

这里和姊妹网站上存在很多问题,例如https://codereview.stackexchange.com/与错误,复杂性以及这些经典排序算法实现的其他方面有关。 大多数提供的实现都由原始循环组成,使用索引操作和具体类型,并且通常在正确性和效率方面不是微不足道的。

问题 :如何使用现代C ++实现上述经典排序算法?

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

备注

  • 有关排序算法实现的进一步参考,请参阅WikipediaRosetta Codehttp://www.sorting-algorithms.com/
  • 根据肖恩家长的惯例 (幻灯片39),原始循环比运算符的两个函数的组合更长。 所以f(g(x));f(x); g(x); f(x); g(x);f(x) + g(x); 不是原始循环,也不是下面的selection_sortinsertion_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的形式呈现。 在相关的地方,我指出各种语言版本不同的语法和库差异。



Links