实现 constexpr 快速排序 ​

面试考点 ​

编译时快速排序是 constexpr 编程的进阶题目。面试官考察你是否理解 C++17/20 constexpr 的能力边界、编译期数组操作、分区算法在 constexpr 中的实现,以及 static_assert 验证编译期结果的技巧。

核心概念 ​

C++17 大幅放宽了 constexpr 的限制:允许循环、条件语句、局部变量。C++20 进一步允许 constexpr 中的动态内存分配(编译期 new/delete,但必须在编译期释放)。这使得在编译期实现完整的快速排序算法成为可能。编译期排序的结果直接嵌入二进制文件,运行时零开销。

基本示例 ​

cpp
#include <iostream>
#include <array>
#include <algorithm>
#include <cstddef>
#include <type_traits>

// ============================
// 方法1:constexpr 函数排序 std::array
// ============================

// C++17 起,std::array 的大部分操作都是 constexpr
// C++20 起,std::sort 也是 constexpr(但这里我们手写)

// constexpr 交换(C++20 中 std::swap 已经是 constexpr)
template<typename T>
constexpr void cx_swap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

// constexpr 分区:Lomuto 分区方案
// 选择最后一个元素作为基准
// 把小于基准的元素放到左边,大于等于的放到右边
template<typename T, size_t N>
constexpr size_t cx_partition(std::array<T, N>& arr, size_t low, size_t high) {
    T pivot = arr[high];   // 基准值
    size_t i = low;        // i 指向下一个要放小元素的位置

    for (size_t j = low; j < high; j++) {
        if (arr[j] < pivot) {
            cx_swap(arr[i], arr[j]);
            i++;
        }
    }

    // 把基准放到正确的位置
    cx_swap(arr[i], arr[high]);
    return i;
}

// constexpr 快速排序(递归)
template<typename T, size_t N>
constexpr void cx_quicksort(std::array<T, N>& arr, size_t low, size_t high) {
    if (low < high) {
        size_t pivot_index = cx_partition(arr, low, high);

        // 递归排序左半部分
        if (pivot_index > 0) {
            cx_quicksort(arr, low, pivot_index - 1);
        }

        // 递归排序右半部分
        cx_quicksort(arr, pivot_index + 1, high);
    }
}

// 对外接口:接收 array,返回排序后的副本
template<typename T, size_t N>
constexpr std::array<T, N> sort_array(std::array<T, N> arr) {
    if constexpr (N > 1) {
        cx_quicksort(arr, 0, N - 1);
    }
    return arr;
}

// ============================
// 编译期验证
// ============================

// 编译期检查数组是否有序
template<typename T, size_t N>
constexpr bool is_sorted(const std::array<T, N>& arr) {
    for (size_t i = 1; i < N; i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}

// 用 static_assert 在编译期验证排序结果
constexpr auto sorted1 = sort_array(std::array{5, 3, 8, 1, 9, 2, 7, 4, 6, 0});
static_assert(is_sorted(sorted1), "排序结果必须有序");
static_assert(sorted1[0] == 0, "最小值应该是 0");
static_assert(sorted1[9] == 9, "最大值应该是 9");

constexpr auto sorted2 = sort_array(std::array{42});
static_assert(sorted2[0] == 42, "单元素数组");

constexpr auto sorted3 = sort_array(std::array{3, 1});
static_assert(sorted3[0] == 1 && sorted3[1] == 3, "两元素排序");

constexpr auto sorted_empty = sort_array(std::array<int, 0>{});
static_assert(sorted_empty.size() == 0, "空数组");

// 已有序的数组
constexpr auto sorted4 = sort_array(std::array{1, 2, 3, 4, 5});
static_assert(is_sorted(sorted4), "已有序数组仍有序");

// 逆序数组
constexpr auto sorted5 = sort_array(std::array{5, 4, 3, 2, 1});
static_assert(sorted5[0] == 1 && sorted5[4] == 5, "逆序数组排序");

// 有重复元素
constexpr auto sorted6 = sort_array(std::array{3, 1, 4, 1, 5, 9, 2, 6, 5, 3});
static_assert(is_sorted(sorted6), "有重复元素的排序");

// ============================
// 方法2:三路快排(处理大量重复元素)
// ============================

// 三路分区:小于/等于/大于基准
template<typename T, size_t N>
constexpr void cx_quicksort_3way(std::array<T, N>& arr, size_t low, size_t high) {
    if (low >= high) return;

    T pivot = arr[low];
    size_t lt = low;       // arr[low..lt-1] < pivot
    size_t gt = high;      // arr[gt+1..high] > pivot
    size_t i = low + 1;    // arr[lt..i-1] == pivot

    while (i <= gt) {
        if (arr[i] < pivot) {
            cx_swap(arr[lt], arr[i]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            cx_swap(arr[i], arr[gt]);
            if (gt == 0) break;
            gt--;
        } else {
            i++;
        }
    }

    // 递归排序小于和大于部分(等于部分已在正确位置)
    if (lt > 0) {
        cx_quicksort_3way(arr, low, lt - 1);
    }
    if (gt < high) {
        cx_quicksort_3way(arr, gt + 1, high);
    }
}

template<typename T, size_t N>
constexpr std::array<T, N> sort_array_3way(std::array<T, N> arr) {
    if constexpr (N > 1) {
        cx_quicksort_3way(arr, 0, N - 1);
    }
    return arr;
}

constexpr auto sorted_3way = sort_array_3way(
    std::array{5, 5, 5, 3, 3, 1, 1, 2, 4, 4}
);
static_assert(is_sorted(sorted_3way), "三路快排结果有序");

// ============================
// 方法3:编译期生成查找表
// ============================

// 应用:编译期生成排序后的查找表
// 用于需要二分查找的静态数据
constexpr auto lookup_table = sort_array(std::array{
    97, 23, 45, 67, 12, 89, 34, 56, 78, 90,
    11, 33, 55, 77, 99, 22, 44, 66, 88, 10
});

// 编译期二分查找
template<typename T, size_t N>
constexpr bool cx_binary_search(const std::array<T, N>& arr, const T& target) {
    size_t left = 0;
    size_t right = N;

    while (left < right) {
        size_t mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return true;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return false;
}

static_assert(cx_binary_search(lookup_table, 45), "45 应该存在");
static_assert(cx_binary_search(lookup_table, 99), "99 应该存在");
static_assert(!cx_binary_search(lookup_table, 50), "50 不应该存在");

// ============================
// 编译期 vs 运行时性能
// ============================

// constexpr 排序的结果直接编入二进制
// 运行时访问的是已排序的常量数组,零计算开销
void print_sorted() {
    std::cout << "编译期排序结果: ";
    for (auto v : sorted1) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    std::cout << "查找表: ";
    for (auto v : lookup_table) {
        std::cout << v << " ";
    }
    std::cout << std::endl;
}

// ============================
// 应用:constexpr 排序 + 去重
// ============================

template<typename T, size_t N>
constexpr auto sort_and_unique(std::array<T, N> arr) {
    // 先排序
    if constexpr (N <= 1) {
        return arr;
    } else {
        cx_quicksort(arr, 0, N - 1);
        return arr;
    }
}

// 编译期计算不重复元素个数
template<typename T, size_t N>
constexpr size_t count_unique(const std::array<T, N>& sorted_arr) {
    if constexpr (N == 0) return 0;
    size_t count = 1;
    for (size_t i = 1; i < N; i++) {
        if (sorted_arr[i] != sorted_arr[i - 1]) {
            count++;
        }
    }
    return count;
}

constexpr auto test_dup = sort_and_unique(std::array{3, 1, 4, 1, 5, 9, 2, 6, 5, 3});
constexpr size_t unique_count = count_unique(test_dup);
static_assert(unique_count == 8, "去重后应有8个不同元素");

int main() {
    print_sorted();

    // 运行时验证编译期结果
    std::cout << "sorted1[0]=" << sorted1[0]
              << " sorted1[9]=" << sorted1[9] << std::endl;

    // 编译期二分查找结果
    std::cout << "查找 45: " << cx_binary_search(lookup_table, 45) << std::endl;
    std::cout << "查找 50: " << cx_binary_search(lookup_table, 50) << std::endl;

    // 去重计数
    std::cout << "不重复元素数: " << unique_count << std::endl;

    return 0;
}

constexpr 在不同标准中的能力 ​

特性C++11C++14C++17C++20
局部变量不支持支持支持支持
循环不支持支持支持支持
条件语句不支持支持支持支持
if constexpr不支持不支持支持支持
std::array 修改不支持支持支持支持
std::sort不是 constexpr不是不是是
动态内存不支持不支持不支持受限支持

Lomuto vs Hoare 分区 ​

分区方案LomutoHoare
基准选择最后一个元素第一个或中间元素
交换次数较多较少
已排序数组O(n^2)O(n^2)(同)
实现复杂度简单稍复杂
constexpr 友好是是

常见问题 ​

编译期排序有什么实际用途?

主要用于静态查找表的生成:把无序的配置数据在编译期排好序,运行时直接用二分查找,零排序开销。还可以用于编译期去重、编译期集合运算等。在嵌入式系统中,编译期计算可以减少运行时的 CPU 和内存开销。

constexpr 快排的递归深度有限制吗?

C++ 标准要求编译器至少支持 512 层 constexpr 递归。快排的平均递归深度是 O(log N),对于 512 的限制,理论上可以排序 2^512 个元素。但实际编译器有编译时间和内存限制,通常几千个元素是合理范围。

为什么 sort_array 接收值而非引用?

constexpr 函数的参数如果要修改,不能是 const 引用。但我们也不想修改原数组。所以按值传入,在函数内修改副本,然后返回排序后的副本。编译器会优化掉不必要的拷贝。

适用场景 ​

  • 静态查找表的编译期生成
  • 嵌入式系统中的零运行时开销排序
  • 编译期数据验证(static_assert 检查数据有效性)
  • 编译期去重和集合运算

注意事项 ​

  • constexpr 排序在编译期执行,大数据量会显著增加编译时间
  • 递归深度有编译器限制,超大数组可能编译失败
  • C++20 的 std::sort 已经是 constexpr,不需要手写(但面试中手写是考点)
  • 编译期动态内存分配(C++20)必须在编译期释放
  • constexpr 函数的参数必须在编译期已知

总结 ​

constexpr 快速排序利用 C++17 放宽的 constexpr 限制,在编译期对 std::array 执行快排。核心是 Lomuto 分区的 constexpr 实现,配合递归排序。用 static_assert 验证编译期结果的正确性。面试中要能手写 constexpr 分区和递归排序函数,用 static_assert 证明排序正确,解释编译期排序的实际用途(查找表生成),以及讨论 constexpr 的递归深度限制。