快速排序是C++开发中高频使用的排序算法，其核心思想是通过一次划分将待排序列分成两部分，使得左侧元素均不大于基准、右侧元素均不小于基准，再对子区间递归处理。理解划分过程的指针移动逻辑，是写出正确且高效快排的前提。
一、快速排序的基础原理与分区逻辑
快排本质上是一种分治算法。选取一个基准值（pivot）后，通过扫描与交换操作让序列局部有序。最经典的霍尔（Hoare）划分使用两个索引从两端向中间逼近：左指针找大于基准的元素，右指针找小于基准的元素，找到后交换，直到相遇。此时相遇点未必是基准最终位置，因此常配合挖坑法或单指针法来简化理解。
下面给出基于挖坑法的划分函数示例。挖坑法先保存基准值，形成第一个坑，右指针左移补坑，左指针右移补坑，最后将基准填入剩余坑位。这种方式逻辑直观，且便于在源码层面追踪每次赋值。
#include <vector>
using namespace std;
// 挖坑法分区，返回基准最终下标
int partition(vector<int>& arr, int left, int right) {
int pivot = arr[left]; // 以最左为基准，挖出第一个坑
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--; // 右侧找小于基准的
if (i < j) arr[i++] = arr[j]; // 补左侧坑，右侧成新坑
while (i < j && arr[i] <= pivot) i++; // 左侧找大于基准的
if (i < j) arr[j--] = arr[i]; // 补右侧坑，左侧成新坑
}
arr[i] = pivot; // 基准入坑
return i;
}
void quickSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int pos = partition(arr, left, right);
quickSort(arr, left, pos - 1);
quickSort(arr, pos + 1, right);
}
上述代码在随机数据下表现良好，但一旦输入序列本身有序或所有元素相等，每次划分都极不均匀，递归深度达到n，时间复杂度退化为O(n^2)，且可能栈溢出。这也是为什么工业级实现必须引入优化。
二、三数取中与随机基准优化
为避免最坏情况，常用三数取中法：比较左端、中间、右端三个位置的元素，取中位数作为基准，并将它交换到左端。这样即使序列有序，中位数也能将区间几乎等分。另一种做法是随机选取基准下标，用rand()打乱选择，概率上规避恶意构造数据。
以下代码展示三数取中的辅助函数及改造后的排序入口。注意比较时要用严格弱序，防止相等元素交换导致死循环。
#include <algorithm>
#include <vector>
using namespace std;
int medianOfThree(vector<int>& a, int l, int r) {
int m = l + (r - l) / 2;
if (a[l] > a[m]) swap(a[l], a[m]);
if (a[l] > a[r]) swap(a[l], a[r]);
if (a[m] > a[r]) swap(a[m], a[r]);
swap(a[m], a[l]); // 中位数放左端
return a[l];
}
int partitionOpt(vector<int>& arr, int left, int right) {
int pivot = medianOfThree(arr, left, right);
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] <= pivot) i++;
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
return i;
}
void quickSortOpt(vector<int>& arr, int left, int right) {
if (left >= right) return;
int pos = partitionOpt(arr, left, right);
quickSortOpt(arr, left, pos - 1);
quickSortOpt(arr, pos + 1, right);
}
三数取中几乎不增加常数开销，却显著提升了面对有序数据的鲁棒性。在实测中，对十万级升序数组，未优化版本耗时陡增，而优化版仍保持毫秒级。不过递归本身仍有栈消耗，需要结合尾递归或循环来削减。
三、尾递归与小数组切换插入排序
快排的递归树深度在理想情况为log n，但极端情况仍可能较深。采用尾递归优化，将较大的子区间用循环处理，仅对较小区间递归，可将额外栈空间降到O(log n)。同时，当子区间长度小于阈值（如16）时，插入排序的局部性更好，可避免快排小数组的函数调用开销。
下面示例合并了尾递归与阈值切换。注意插入排序需用简单双层循环，且快排循环部分手动更新边界。
#include <vector>
using namespace std;
void insertionSort(vector<int>& a, int l, int r) {
for (int i = l + 1; i <= r; i++) {
int key = a[i], j = i - 1;
while (j >= l && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
void quickSortHybrid(vector<int>& arr, int left, int right) {
while (left < right) {
if (right - left < 16) {
insertionSort(arr, left, right);
break;
}
int pos = partitionOpt(arr, left, right);
// 优先递归较小侧，较大侧用循环
if (pos - left < right - pos) {
quickSortHybrid(arr, left, pos - 1);
left = pos + 1;
} else {
quickSortHybrid(arr, pos + 1, right);
right = pos - 1;
}
}
}
这种混合策略与C++标准库std::sort的内省排序思路接近：在快排递归深度超限时改堆排序，小数组用插入排序。掌握这些源码级技巧，你便能针对具体业务写出可控、可预测的排序组件，而不只是调用现成接口。
四、常见误区与等价比较注意点
一个隐蔽错误是在划分时把判断写成arr[j] > pivot而漏掉等号，或对左右指针使用相同等号导致相等元素频繁交换、递归区间不收缩。快排要求划分后基准不参与子区间，因此pos-1与pos+1的边界必须准确。若用霍尔原始版本，返回相遇点后还需交换基准，容易写出越界。
此外，对自定义类型排序时，比较函数必须满足严格弱序：若a<b与b<a皆假则视为等价，不可在等价时返回真。否则标准库或自写快排都可能进入无限递归。建议在泛型化快排时用std::less而非手写大于小于，减少出错概率。
template<typename T, typename Compare>
int partitionGeneric(T* a, int l, int r, Compare cmp) {
T pivot = a[l];
int i = l, j = r;
while (i < j) {
while (i < j && !cmp(a[j], pivot)) j--;
if (i < j) a[i++] = a[j];
while (i < j && !cmp(pivot, a[i])) i++;
if (i < j) a[j--] = a[i];
}
a[i] = pivot;
return i;
}
综上，C++快排从基础分区到三数取中、尾递归、混合排序，是一条清晰的进阶路线。读懂源码每一处边界与比较，才能在性能与稳定性间取得平衡。
C++quick_sortpartition_optimization修改时间：2026-08-04 11:39:38