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

Question

来自 C++ 标准库的 std::sort 算法（及其表亲 std::partial_sort 和 std::nth_element ）在大多数 更基本的算法中是一种复杂、混合的混合算法 如选择排序、插入排序、快速排序、合并排序或堆排序。

这里和姊妹网站上有很多问题，例如 https://codereview.stackexchange.com/ 与这些经典排序算法实现的错误、复杂性和其他方面相关。大多数提供的实现由原始循环、使用索引操作和具体类型组成，并且通常在正确性和效率方面进行分析并非易事。

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

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

备注：

• 有关排序算法实现的进一步参考，请参见 Wikipedia 、 Rosetta Code 或 http://www.sorting-algorithms.com/
• 根据 Sean Parent 的约定（幻灯片 39），原始循环是 for 循环比使用运算符的两个函数组合更长。 So f(g(x)); or f(x); g(x); or f(x) + g(x); are not raw loops, and neither are the loops in selection_sort and 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 的形式呈现。在相关的地方，我表示各种语言版本不同的句法和库差异。

原文由 TemplateRex 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

算法构建块

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

 #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::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 提供了 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 有助于通过 多态 lambda 封装用户定义的比较器（使用 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 的 草稿 Effective Modern C++ 和 Herb Sutter 修改后的 GotW 。我使用以下样式建议：

• Herb Sutter 的 “Almost Always Auto” 和 Scott Meyers 的 “Prefer auto to specific type declarations” 建议的简洁性是无与伦比的，尽管其清晰度有时 存在争议。
• Scott Meyers’s “Distinguish () and {} when creating objects” and consistently choose braced-initialization {} instead of the good old parenthesized initialization () （为了回避通用代码中所有最棘手的解析问题）。
• Scott Meyers 的 “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) 输入范围的中值。

细节省略：

• 上述实现特别容易受到特殊输入的影响，例如它具有 O(N^2) “ 风琴管”输入的复杂性 1, 2, 3, ..., N/2, ... 3, 2, 1 （因为中间总是大于所有其他元素）。
• 从输入范围中 随机选择的元素 中选择 3 的中值 可以防止几乎排序的输入，否则复杂性会恶化到 O(N^2) 。
• 如对 std::partition 的两次调用所示， 三向分区（分隔小于、等于和大于枢轴的元素）并不是实现此结果的最有效的 O(N) 算法。
• for random access iterators , a guaranteed O(N log N) complexity can be achieved through median pivot selection using std::nth_element(first, middle, last) , followed by recursive calls to quick_sort(first, middle, cmp) and quick_sort(middle, last, cmp) 。
• 但是，这种保证是有代价的，因为 --- 的 O(N) 复杂性的常数因子可能比中位数的 std::nth_element O(1) 复杂性的常数因子更昂贵-of-3 pivot 后跟 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) “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::pop_heap “作弊”，您可以更深入一层并根据 std::push_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) 。 Note however that the outer loop over the range [first, last) results in O(N log N) complexity for make_heap , whereas std::make_heap has only O(N) 复杂性。对于整体 O(N log N) 复杂度 heap_sort 没关系。

细节省略： O(N) 实现 make_heap

测试

这里有四个 实时示例（ C++14 、 C++11 、 C++98 和 Boost 、 C++98 ）在各种输入上测试所有五种算法（并不意味着详尽或严格）。请注意 LOC 的巨大差异：C++11/C++14 需要大约 130 LOC，C++98 和 Boost 190 (+50%) 和 C++98 超过 270 (+100%)。

原文由 TemplateRex 发布，翻译遵循 CC BY-SA 4.0 许可协议