编译期排序：冒泡排序与快速排序的模板元实现

排序算法，咱们平时写业务代码时天天用。但你想过没有——这些排序能不能在编译期完成？

说白了，就是让编译器替你把数组排好序，运行时直接拿结果。我刚开始接触模板元编程时，觉得这事挺玄乎。后来在做一个嵌入式项目，需要在启动阶段就用到一个有序的查找表，运行时排序会拖慢初始化速度。嗯，那时候我就认真研究了一把编译期排序。

今天咱们就聊聊两种经典排序的模板元实现：冒泡排序和快速排序。一个简单直观，一个高效优雅。

为什么要在编译期排序？

先说说实际场景。我在项目中遇到过这样的情况：

• 需要根据某些编译期常量生成一个有序的配置表
• 模板元编程中，需要按特定顺序处理类型列表
• 嵌入式系统里，运行时排序会占用宝贵的CPU周期

编译期排序的好处很明显：零运行时开销，排序结果直接硬编码到二进制里。代价就是——代码写起来确实有点绕。

冒泡排序的模板元实现

冒泡排序的思路很简单：从左到右，两两比较，把大的往后冒。重复 n-1 轮。

模板元实现时，我们需要把每一轮比较和交换拆解成模板递归。来看代码：

// 前置声明
template<typename Seq, bool Swapped>
struct bubble_sort_pass;

// 辅助：交换两个值
template<int A, int B>
struct swap_pair {
    static constexpr int first = B;
    static constexpr int second = A;
};

// 不交换的情况
template<int A, int B>
struct no_swap {
    static constexpr int first = A;
    static constexpr int second = B;
};

// 单次比较和交换
template<int A, int B, bool Cond>
struct compare_and_swap;

template<int A, int B>
struct compare_and_swap<A, B, true> {  // A > B，需要交换
    using type = swap_pair<A, B>;
};

template<int A, int B>
struct compare_and_swap<A, B, false> { // A <= B，不交换
    using type = no_swap<A, B>;
};

// 一轮冒泡：处理序列中的一对元素
template<int... Args>
struct bubble_sort_pass<std::integer_sequence<int, Args...>, false> {
    // 递归终止：没有发生交换，排序完成
    using type = std::integer_sequence<int, Args...>;
};

// 实际实现（简化版，展示核心逻辑）
template<int First, int Second, int... Rest>
struct bubble_sort_pass<std::integer_sequence<int, First, Second, Rest...>, true> {
    // 比较 First 和 Second
    using cmp = compare_and_swap<First, Second, (First > Second)>;
    
    // 递归处理剩余部分
    using next_pass = bubble_sort_pass<
        std::integer_sequence<int, 
            cmp::type::first,  // 交换后的第一个值
            cmp::type::second, // 交换后的第二个值
            Rest...>,
        (First > Second)       // 是否继续
    >;
    
    using type = typename next_pass::type;
};

冒泡排序的模板元实现，说白了就是两层递归：外层控制轮数，内层控制每轮的比较交换。代码量不大，但递归深度会随着元素数量线性增长。对于几十个元素的编译期排序，完全够用。

快速排序的模板元实现

快速排序就优雅多了。分治思想，选一个 pivot，把小于它的放左边，大于它的放右边，然后递归处理左右两边。

模板元实现快排，核心是三个步骤：

1. 从序列中选出 pivot（通常取第一个元素）
2. 将剩余元素分成两组：小于 pivot 的和大于等于 pivot 的
3. 递归排序两组，然后拼接起来

看代码：

// 快速排序主模板
template<typename Seq>
struct quick_sort;

// 辅助：将整数序列分成两部分
template<int Pivot, int... Args>
struct partition {
    // 递归拆分
    template<int... Left, int... Right>
    struct impl;
    
    // 最终结果
    using left_seq = std::integer_sequence<int, /* 小于 pivot 的元素 */>;
    using right_seq = std::integer_sequence<int, /* 大于等于 pivot 的元素 */>;
};

// 快速排序实现
template<int First, int... Rest>
struct quick_sort<std::integer_sequence<int, First, Rest...>> {
private:
    // 以 First 为 pivot，划分剩余元素
    using partition_result = partition<First, Rest...>;
    
    // 递归排序左右两部分
    using sorted_left = quick_sort<typename partition_result::left_seq>;
    using sorted_right = quick_sort<typename partition_result::right_seq>;
    
public:
    // 拼接：左 + pivot + 右
    using type = /* 拼接后的 integer_sequence */;
};

// 递归终止：空序列或单元素序列
template<>
struct quick_sort<std::integer_sequence<int>> {
    using type = std::integer_sequence<int>;
};

template<int Only>
struct quick_sort<std::integer_sequence<int, Only>> {
    using type = std::integer_sequence<int, Only>;
};

两种实现的对比

维度	冒泡排序	快速排序
实现复杂度	简单直观，容易理解	中等，需要处理划分逻辑
编译期递归深度	O(n²)，元素多时可能超限	平均 O(log n)，最坏 O(n)
编译速度	较慢，尤其是大序列	较快，分治策略更优
适用场景	小规模（< 20 个元素）	中等规模（< 100 个元素）
代码可读性	高，一眼能看懂	中等，需要理解分治思想

我个人习惯是：小数据用冒泡，大数据用快排。如果元素少于 10 个，冒泡的代码更清晰，编译也快。超过 20 个，果断上快排。

核心逻辑流程图

下面这张图展示了两种排序在模板元层面的核心流程对比：

实际使用中的注意事项

写编译期排序时，有几个坑我踩过，分享给你：

• 递归深度限制：编译器默认模板递归深度是 256 或 512。如果你的序列有 100 个元素，冒泡排序需要 100 轮，每轮递归深度可能达到 100，加起来就超了。可以用 -ftemplate-depth 调整，但不建议依赖这个。
• 编译时间：模板元排序的编译时间比运行时排序慢得多。我试过对 50 个整数做快排，编译花了将近 2 秒。所以只适合小规模数据。
• 类型列表排序：除了整数，你还可以对类型列表排序。比如按类型的大小、按名称的哈希值等。原理一样，只是比较函数换成类型萃取。

好了，编译期排序就聊到这儿。两种实现各有千秋，关键是根据你的数据规模选择合适的方案。记住一点：编译期计算虽然强大，但也不是万能的。该用运行时排序的时候，别硬上模板元。

---

公众号:蓝海资料掘金营，微信deep3321