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


Answers

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

计数排序

虽然它是相当专业的,但计数排序是一种简单的整数排序算法,通常可以非常快速地提供排序的整数的值不会相差太远。 例如,如果有人需要对一百万个整数进行排序,那么这可能是理想的。

为了实现一个非常简单的计数排序,它与签名和无符号整数一起使用,需要在集合中找到要排序的最小和最大的元素; 他们的差异将告诉要分配的计数数组的大小。 然后,第二次通过集合来计算每个元素的出现次数。 最后,我们将所需的每个整数的数量写回原始集合。

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);
    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传播码

细节省略

  • 我们可以将算法接受的值范围的范围作为参数传递,以完全摆脱通过集合的第一个std::minmax_element传递。 当边界已经被其他方式所了解时,这可能会使算法更快。

  • 在上面的算法中,当每个元素具有相同的值(在这种情况下,集合被排序)时,我们使用一个min == max检查来提早返回。 实际上可以完全检查集合是否已经排序,同时找到集合的极限值,而不会浪费额外的时间,使得算法返回提前,并且在集合已经排序时不分配内存。 然而,这种算法在标准库中并不存在,而编写一个算法比编写其余的计数排序本身将会更加乏味。 留给读者的锻炼。

  • 由于该算法仅适用于整数值,静态断言可用于防止用户出现明显的类型错误。 在某些情况下,可能会使用std::enable_if_t替换失败。

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

Question

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

这里有许多问题和姊妹网站,例如https://codereview.stackexchange.com/涉及到这些经典排序算法的错误,复杂性和其他方面的实现。 大多数提供的实现包括原始循环,使用索引操作和具体类型,并且在正确性和效率方面通常是不重要的。

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

  • 没有原始循环 ,而是结合了标准库的算法构建块与<algorithm>
  • 迭代器接口和使用模板,而不是索引操作和具体类型
  • C ++ 14样式 ,包括完整的标准库,以及语法降噪器,如auto ,模板别名,透明比较器和多态性的lambdas。

注意

  • 有关排序算法实现的进一步参考,请参阅维基百科Rosetta代码http://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表示。 在相关的情况下,我表示各种语言版本不同的句法和图书馆差异。