C++怎么实现快速排序 C++ quick_sort算法递归与非递归写法【考研】

递归版 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& a, int left, int right) {
    int pivot = a[left];
    while (left < right) {
        while (left < right && a[right] >= pivot) right--;
        a[left] = a[right];
        while (left < right && a[left] <= pivot) left++;
        a[right] = a[left];
    }
    a[left] = pivot;
    return left;
}
void quick_sort(vector& 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);
}

非递归版用 stack 模拟时栈里存什么

非递归本质是手动管理递归调用栈，但考研现场手写容易堆栈元素类型混乱——存数组指针？存下标对？存结构体？最稳妥的是只存两个 int：左边界和右边界。

错误做法：压入单个索引、压入指针（C++ 中易悬空）、或每次压入四个数（如左右+pivot），增加调试难度且不符合考题简洁要求。

立即学习“C++免费学习笔记（深入）”；

萝卜简历

免费在线AI简历制作工具，帮助求职者轻松完成简历制作。

下载

• 用 stack> 或两个 stack，推荐前者，语义清晰
• 初始压入 {0, n-1}，每次弹出一对 (l, r)，做完 partition 后，仅当子区间合法才压入——即 if (l ，if (p+1
• 注意：非递归版的 partition 必须与递归版完全一致，否则行为不等价

void quick_sort_iterative(vector& a) {
    int n = a.size();
    if (n <= 1) return;
    stack> 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 < p - 1) stk.push({l, p - 1});
        if (p + 1 < r) stk.push({p + 1, r});
    }
}

考研笔试里要不要写随机化 pivot

标准快排最坏时间复杂度 O(n²)，出现在已排序或逆序输入时。但考研算法题几乎从不考察性能优化，而是考逻辑正确性与边界控制能力。随机化 pivot 虽能规避最坏情况，反而会引入额外考点（如 rand() 初始化、取模边界），增加出错概率。

• 除非题目明确要求「期望时间复杂度 O(n log n)」，否则默认用首元素或中点作 pivot 即可
• 若真要加随机化，务必写 srand(time(0))（虽然笔试不运行，但写全更稳妥），且 swap(a[left], a[left + rand() % (right - left + 1)]) 避免 % 为 0 的崩溃
• 更现实的做法：在 partition 前加一句 swap(a[left], a[(left + right) / 2]);，简单破序又不引入新依赖

vector 传参用引用还是指针

考研 C++ 代码题中，函数参数必须高效且无歧义。传 vector 值会触发深拷贝，O(n) 开销且可能超时；传指针需额外判空，还易写成 vector* a 导致解引用错误。

• 一律用 vector& 引用，既避免拷贝，又保持语法简洁
• 不要写 const vector&——因为要原地排序，必须可修改
• 如果题目给的是普通数组（如 int a[]），则用 int* + len 参数，此时 partition 中所有下标运算都基于指针偏移，别混用 vector 语法

真正容易丢分的地方不在算法本身，而在：分区后忘了把 pivot 放回、递归调用写反了左右顺序、非递归压栈漏判区间长度、或者笔试时用 std::sort 直接交卷——那不算实现 quick_sort。