实现 constexpr 快速排序
面试考点
编译时快速排序是 constexpr 编程的进阶题目。面试官考察你是否理解 C++17/20 constexpr 的能力边界、编译期数组操作、分区算法在 constexpr 中的实现,以及 static_assert 验证编译期结果的技巧。
核心概念
C++17 大幅放宽了 constexpr 的限制:允许循环、条件语句、局部变量。C++20 进一步允许 constexpr 中的动态内存分配(编译期 new/delete,但必须在编译期释放)。这使得在编译期实现完整的快速排序算法成为可能。编译期排序的结果直接嵌入二进制文件,运行时零开销。
基本示例
#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++11 | C++14 | C++17 | C++20 |
|---|---|---|---|---|
| 局部变量 | 不支持 | 支持 | 支持 | 支持 |
| 循环 | 不支持 | 支持 | 支持 | 支持 |
| 条件语句 | 不支持 | 支持 | 支持 | 支持 |
| if constexpr | 不支持 | 不支持 | 支持 | 支持 |
| std::array 修改 | 不支持 | 支持 | 支持 | 支持 |
| std::sort | 不是 constexpr | 不是 | 不是 | 是 |
| 动态内存 | 不支持 | 不支持 | 不支持 | 受限支持 |
Lomuto vs Hoare 分区
| 分区方案 | Lomuto | Hoare |
|---|---|---|
| 基准选择 | 最后一个元素 | 第一个或中间元素 |
| 交换次数 | 较多 | 较少 |
| 已排序数组 | 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 的递归深度限制。