递归版 quick_sort 需确保分区后左右子区间不越界：若 partition 返回 pivot_idx，则左递归为 quick_sort(arr, left, pivot_idx-1)，右递归为 quick_sort(arr, pivot_idx+1, right)，并以 left >= right 为终止条件。
递归版 quick_sort 怎么写才不越界
递归实现的核心是分区（partition）+ 递归调用左右子区间，但考研代码题常因边界处理出错导致段错误或死循环。关键在于 partition 返回的基准索引是否能安全划分区间。
常见错误：把 left 和 right 当成闭区间却用开区间逻辑递归，比如写成 quick_sort(arr, i+1, right) 却没保证 i+1 ；或者 partition 返回值未严格落在 [left, right] 内。
- 统一用闭区间
[left, right]，递归前必须判断if (left >= right) return; -
partition推荐使用「挖坑法」或「双指针法」，避免交换后漏判；返回值应为基准最终位置pivot_idx，且满足left - 递归调用写成
quick_sort(arr, left, pivot_idx - 1)和quick_sort(arr, pivot_idx + 1, right)，确保子区间不重叠、不越界
int partition(vector<int>& a, int left, int right) {
int pivot = a[left];
while (left = pivot) right--;
a[left] = a[right];
while (left void quick_sort(vector<int>& a, int left, int right) {
if (left >= right) return;
int p = partition(a, left, right);
quick_sort(a, left, p - 1);
quick_sort(a, p + 1, right);
}</int></int>
非递归版用 stack 模拟时栈里存什么
非递归本质是手动管理递归调用栈，但考研现场手写容易堆栈元素类型混乱——存数组指针？存下标对？存结构体？最稳妥的是只存两个 int：左边界和右边界。
错误做法：压入单个索引、压入指针（C++ 中易悬空）、或每次压入四个数（如左右+pivot），增加调试难度且不符合考题简洁要求。
- 用
stack或两个> stack，推荐前者，语义清晰 - 初始压入
{0, n-1}，每次弹出一对(l, r)，做完partition后，仅当子区间合法才压入——即if (l ，if (p+1 - 注意：非递归版的
partition必须与递归版完全一致，否则行为不等价
void quick_sort_iterative(vector<int>& a) {
int n = a.size();
if (n > stk;
stk.push({0, n - 1});
while (!stk.empty()) {
auto [l, r] = stk.top(); stk.pop();
if (l >= r) continue;
int p = partition(a, l, r);
if (l <h3>考研笔试里要不要写随机化 pivot</h3>
<p>标准快排最坏时间复杂度 O(n²)，出现在已排序或逆序输入时。但考研算法题几乎从不考察性能优化，而是考逻辑正确性与边界控制能力。随机化 <code>pivot</code> 虽能规避最坏情况，反而会引入额外考点（如 <code>rand()</code> 初始化、取模边界），增加出错概率。</p>
<ul>
<li>除非题目明确要求「期望时间复杂度 O(n log n)」，否则默认用首元素或中点作 <code>pivot</code> 即可</li>
<li>若真要加随机化，务必写 <code>srand(time(0))</code>（虽然笔试不运行，但写全更稳妥），且 <code>swap(a[left], a[left + rand() % (right - left + 1)])</code> 避免 <code>%</code> 为 0 的崩溃</li>
<li>更现实的做法：在 <code>partition</code> 前加一句 <code>swap(a[left], a[(left + right) / 2]);</code>，简单破序又不引入新依赖</li>
</ul>
<h3>vector 传参用引用还是指针</h3>
<p>考研 C++ 代码题中，函数参数必须高效且无歧义。传 <code>vector<int></int></code> 值会触发深拷贝，O(n) 开销且可能超时；传指针需额外判空，还易写成 <code>vector<int>* a</int></code> 导致解引用错误。</p>
<ul>
<li>一律用 <code>vector<int>&</int></code> 引用，既避免拷贝，又保持语法简洁</li>
<li>不要写 <code>const vector<int>&</int></code>——因为要原地排序，必须可修改</li>
<li>如果题目给的是普通数组（如 <code>int a[]</code>），则用 <code>int*</code> + <code>len</code> 参数，此时 <code>partition</code> 中所有下标运算都基于指针偏移，别混用 <code>vector</code> 语法</li>
</ul>
<p>真正容易丢分的地方不在算法本身，而在：分区后忘了把 pivot 放回、递归调用写反了左右顺序、非递归压栈漏判区间长度、或者笔试时用 <code>std::sort</code> 直接交卷——那不算实现 quick_sort。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
