应优先递归处理较小的子数组并显式循环处理较大的子数组，同时对长度≤10的子数组改用插入排序，可将最坏递归深度从O(n)降至O(log n)。
快速排序的递归结构怎么写才不栈溢出
递归实现快排时，最常踩的坑是没控制好递归深度，尤其在输入已接近有序时，partition 每次只减少一个元素，导致 O(n) 层递归，容易触发栈溢出（尤其考研机试环境栈空间小）。必须用「尾递归优化」或「小数组转插入排序」来缓解。
实操建议：
- 对子数组长度
right - left + 1 的情况，直接调用insertion_sort，避免浅层递归开销 - 递归调用前，先处理较短的子区间，再用循环处理较长的——这能将最坏栈深度压到 O(log n)
- 不要写成
quick_sort(left, pivot-1); quick_sort(pivot+1, right);这种裸递归，它不保证栈深度
partition 函数选哪个版本更稳妥（Lomuto vs Hoare）
考研代码题里，Hoare 分区虽然交换次数少、边界处理紧凑，但初学者极易写错指针越界（比如 ++i 后没判 i 就访问 arr[i]）；Lomuto 更直观，但对全相同元素退化严重（每次只缩一格）。
推荐用改良版 Lomuto，加随机化 pivot：
立即学习“C++免费学习笔记（深入）”；
int partition(vector& arr, int left, int right) { int idx = left + rand() % (right - left + 1); swap(arr[idx], arr[right]); // 随机选 pivot 并换到末尾 int pivot = arr[right]; int i = left; for (int j = left; j < right; ++j) { if (arr[j] <= pivot) { swap(arr[i++], arr[j]); } } swap(arr[i], arr[right]); return i; }
注意：rand() 要提前调 srand(time(0))，但机试中若禁止 time()，可用 std::random_device 或固定种子（如 srand(42)）
如何让快排稳定（考研偶尔考“稳定快排”变种）
标准快排本质不稳定——因为 partition 中相等元素可能跨距交换。真要稳定，不能靠改比较逻辑，得换策略：
- 放弃原地排序，用额外空间：把小于、等于、大于 pivot 的元素分别存入三个 vector，再合并回原数组
- 改用「三路快排」（Dutch National Flag）：返回
[lt, gt]区间，使arr[left..lt-1] ，arr[lt..gt] == pivot，arr[gt+1..right] > pivot；这样相等元素不会乱序移动 - 考研若明确要求“稳定”，大概率是陷阱题——快排无法在 O(1) 空间 + O(n log n) 时间下稳定，应立刻质疑题干，或转向归并
STL sort 是不是快排？能不能直接用在考研机试
std::sort 在大多数 STL 实现中是「 introsort 」——快排 + 堆排序兜底 + 插入排序收尾，平均 O(n log n)，最坏也 O(n log n)。但它内部逻辑黑盒，考试中若题目明确要求“手写快排”，用 std::sort 会判零分。
另外要注意：
- 某些 OJ 禁用
-
std::sort默认升序，降序需传greater，别漏写括号() - 如果数组是
vector，记得传v.begin(), v.end()，不是v, v + n
真正难的不是写出快排，而是想清楚 pivot 怎么选、分区边界怎么控、递归怎么剪、以及什么时候该放弃快排去用归并——这些才是考研现场卡住人的地方。
