首页 文章

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

提问于
浏览 次
302

C标准库中的 std::sort 算法（及其堂兄 std::partial_sort 和 std::nth_element ）在大多数实现中都是a complicated and hybrid amalgamation of more elementary sorting algorithms，例如选择排序，插入排序，快速排序，合并排序或堆排序 .

这里和姊妹网站上存在许多问题，例如与错误，复杂性以及这些经典排序算法的实现的其他方面相关的https://codereview.stackexchange.com/ . 大多数提供的实现包括原始循环，使用索引操作和具体类型，并且在正确性和效率方面通常是非常简单的分析 .

Question ：如何使用现代C实现上述经典排序算法？

  • no raw loops ，但结合了标准库的算法构建块 <algorithm>

  • iterator interface 并使用 templates 而不是索引操作和具体类型

  • C++14 style ，包括完整的标准库，以及语法降噪器，如 auto ，模板别名，透明比较器和多态lambda .

Notes ：

  • 有关排序算法实现的进一步参考，请参阅Wikipedia，Rosetta Code或http://www.sorting-algorithms.com/

  • 根据Sean Parent's conventions（幻灯片39），一个原始循环比一个运算符的两个函数的组合长 for -loop . 所以 f(g(x)); 或 f(x); g(x); 或 f(x) + g(x); 不是原始循环，也不是下面的 selection_sort 和 insertion_sort 中的循环 .

  • 我跟着斯科特迈耶斯's terminology to denote the current C++1y already as C++14, and to denote C++98 and C++03 both as C++98, so don'为此呐喊我 .

  • 正如@Mehrdad的评论中所建议的那样，我在答案的最后提供了四个实现作为实例：C 14，C 11，C 98和Boost和C 98 .

  • 答案本身仅以C 14表示 . 在相关的地方，我表示各种语言版本不同的语法和库差异 .

c++ algorithm sorting c++14 c++-faq

2 回答

  • 13

    算法构建块

    我们首先从标准库中组装算法构建块：

    #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() 仅在C11及更高版本中可用 . 对于C 98，人们需要自己写这些 . 在 boost::begin() / boost::end() 中有Boost.Range的替代品，在 boost::next() 中有来自Boost.Utility的替代品 .

    • std::is_sorted 算法仅适用于C 11及更高版本 . 对于C 98，这可以用 std::adjacent_find 和手写函数对象实现 . Boost.Algorithm还提供 boost::algorithm::is_sorted 作为替代 .

    • std::is_heap 算法仅适用于C 11及更高版本 .

    句法上的好东西

    C 14提供了transparent comparators形式 std::less<> ，它们的参数多态化 . 这样就不必提供迭代器's type. This can be used in combination with C++11' s default function template arguments来创建 a single overload 用于排序算法，这些算法将 < 作为比较，并且具有用户定义的比较函数对象 .

    template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

    在C 11中，可以定义一个可重用的template alias来提取迭代器's value type which adds minor clutter to the sort algorithms'签名：

    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有助于通过 polymorphic lambdas 包装用户定义的比较器（其中 auto 参数被推断为类似函数模板参数） .

    • C 11只有单形lambda，需要使用上面的模板别名 value_type_t .

    • 在C 98中，要么需要编写独立的函数对象，要么使用详细的 std::bind1st / std::bind2nd / std::not1 类型的语法 .

    • Boost.Bind通过 boost::bind 和 _1 / _2 占位符语法改进了这一点 .

    • C 11及更高版本也有 std::find_if_not ，而C 98需要 std::find_if ，并且函数对象周围有 std::not1 .

    C风格

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

    • Herb Sutter的"Almost Always Auto"和Scott Meyers的推荐，其简洁性是无与伦比的，尽管它的清晰度有时是disputed .

    • Scott Meyers的"Distinguish () and {} when creating objects"并始终选择支撑初始化 {} 而不是旧的括号初始化 () （为了在通用代码中支持所有最棘手的解析问题） .

    • Scott Meyers的"Prefer alias declarations to typedefs" . 对于模板而言，无论如何这是必须的，并且在任何地方使用它而不是 typedef 可以节省时间并增加一致性 .

    • 我在某些地方使用 for (auto it = first; it != last; ++it) 模式，以便允许对已经排序的子范围进行循环不变检查 . 在 生产环境 代码中，在循环内部某处使用 while (first != last) 和 ++first 可能稍好一些 .

    选择排序

    Selection sort不以任何方式适应数据，因此其运行时始终为 O(N²) . 但是，选择排序具有 minimizing the number of swaps 的属性 . 在应用程序中的成本交换项目很高，选择排序很好可能是选择的算法 .

    要使用标准库实现它，请重复使用 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 的随机访问迭代器相比，最低要求是 forward iterators .

    Details omitted ：

    可以使用早期测试 if (std::distance(first, last) <= 1) return; （或对于正向/双向迭代器： if (first == last || std::next(first) == last) return; ）优化

    • 选择排序 .

    • for bidirectional iterators ，上述测试可以在 [first, std::prev(last)) 区间内与循环组合，因为最后一个元素保证是最小剩余元素并且不需要交换 .

    插入排序

    虽然它是具有 O(N²) 最坏情况时间的基本排序算法之一，但是当数据几乎排序时（因为它是 adaptive ）或者当问题大小很小（因为它具有低开销）时，insertion sort是选择的算法 . 由于这些原因，并且因为它也是 stable ，插入排序通常用作递归基本情况（当问题大小很小时），用于更高开销的分而治之的排序算法，例如合并排序或快速排序 .

    要使用标准库实现 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) 排序为其循环不变量 . 插入排序也适用于前向迭代器 .

    Details omitted ：

    • 插入排序可以通过早期测试 if (std::distance(first, last) <= 1) return; （或前向/双向迭代器： if (first == last || std::next(first) == last) return; ）和区间 [std::next(first), last) 上的循环进行优化，因为第一个元素保证就位并且不需要旋转 .

    • for bidirectional iterators ，使用标准库的 std::find_if_not 算法可以用 reverse linear search 替换找到插入点的二进制搜索 .

    下面的片段有四个 Live Examples （C++14，C++11，C++98 and 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) 比较 .

    • 对于小输入范围，线性搜索的更好的内存局部性（缓存，预取）也可能支配二进制搜索（当然，应该对此进行测试） .

    快速排序

    仔细实施时，quick sort是健壮的，并且具有预期的复杂性，但具有 O(N²) 最坏情况的复杂性，可以通过对侧选择的输入数据触发 . 如果不需要稳定排序，快速排序是一种出色的通用排序 .

    即使对于最简单的版本，使用标准库实现快速排序比使用其他经典排序算法要复杂得多 . 下面的方法使用一些迭代器实用程序来定位输入范围 [first, last) 的 middle element 作为枢轴，然后使用两次调用 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) 复杂性，枢轴必须导致输入数据的 balancer 分区，这通常不能保证 O(1) 枢轴，但如果将枢轴设置为输入范围的 O(N) 中位数，则可以保证 .

    Details omitted ：

    • 上述实施特别容易受到特殊投入的影响，例如：它具有 O(N^2) 复杂性的“ organ pipe ”输入 1, 2, 3, ..., N/2, ... 3, 2, 1 （因为中间总是大于所有其他元素） .

    • median-of-3来自输入范围的randomly chosen elements的枢轴选择防范几乎已排序的输入，否则复杂性将恶化到 O(N^2) .

    • 3-way partitioning（分隔小于，等于和大于枢轴的元素），如两次调用 std::partition 所示，并不是实现此结果的最有效的算法 .

    • for random access iterators ，保证 O(N log N) 复杂性可以通过 median pivot selection 使用 std::nth_element(first, middle, last) 实现，然后递归调用 quick_sort(first, middle, cmp) 和 quick_sort(middle, last, cmp) .

    • 这种保证是有代价的，因为 std::nth_element 的复杂度的常数因素可能比中位数为3的枢轴的 O(1) 复杂度更高，然后 O(N) 调用 std::partition （这是一个缓存） - 友好的单向前传递数据） .

    合并排序

    如果使用 O(N) 额外的空间是没有的关注，那么merge sort是一个很好的选择：它是唯一的 stable 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 实现 .

    堆排序

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

    第一个循环 O(N) "heapify"阶段将数组置于堆顺序中 . 第二个循环 O(N log N ）"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));
}

    如果您认为它"cheating"使用 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) 复杂性并不重要 .

    Details omitted ：O(N) implementation of make_heap

    测试

    这里有四个 Live Examples （C++14，C++11，C++98 and Boost，C++98）在各种输入上测试所有五种算法（并不是详尽无遗或严格的） . 请注意LOC中的巨大差异：C 11 / C 14需要大约130 LOC，C 98和Boost 190（50％）以及C 98大于270（100％） .

    回复于
  • 363

    另一个小而优雅的originally found on code review . 我认为值得分享 .

    计数排序

    虽然它是相当专业的，counting sort是一个简单的整数排序算法，并且通常可以非常快，只要排序的整数值不是太远 . 如果有人需要对已知在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++);
    }
}

    虽然只有在要排序的整数范围很小（通常不大于要排序的集合的大小）时才有用，但使计数排序更通用会使其在最佳情况下变慢 . 如果不知道该范围很小，则可以使用另一种算法，例如radix sort，ska_sort或spreadsort .

    Details omitted ：

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

    • 在飞行中增长 counts 是避免单独第一次通过的另一种方法 . 每次必须增长时加倍 counts 大小，每个排序元素的停顿时间为O（1）（请参阅散列表插入成本分析，以证明指数增长是关键） . 最后为新的 max 增长很容易 std::vector::resize 添加新的归零元素 . 在生长矢量后，可以使用 std::copy_backward 动态更改 min 并在前面插入新的归零元素 . 然后 std::fill 将新元素归零 .

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

    • 在上面的算法中，我们使用 min == max 检查在每个元素具有相同值时（在这种情况下对集合进行排序）提前返回 . 实际上可以完全检查集合是否已经排序，同时在没有浪费额外时间的情况下找到集合的极值（如果第一遍仍然存在内存瓶颈更新min和max的工作） . 然而，在标准库中不存在这样的算法，并且编写一个算法比编写其余的计数排序本身更繁琐 . 它留给读者练习 .

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

    • 虽然现代C酷，但未来的C可能更酷：structured bindings和Ranges TS的某些部分会使算法更清晰 .

    回复于

相关问题