手写 partition 函数需用 left

partition 函数怎么写才不越界

标准库 std::partition 用起来方便，但手写分区逻辑时最容易在边界上出错——尤其是当输入是空容器、单元素、或所有元素都满足/都不满足谓词时。partition 的核心是双指针向中间收缩，但「谁先动」「停在哪」「交换条件」稍有偏差就会访问 arr[-1] 或跳过最后一个有效位置。

• 用 left 作循环条件，不是 <code>；否则最后一次迭代后 <code>left 可能等于 right，再自增就溢出
• 内层移动指针前必须先检查索引有效性：比如 while (left ，缺了 <code>left 就可能越界
• 交换后要立刻推进指针（left++ 和 right--），否则可能原地死循环

示例（Lomuto 风格，pivot 固定取末尾）：

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

快排递归调用时区间怎么切才不漏元素

分区返回的是 pivot 最终位置 p，接下来递归左右两段。常见错误是把 [low, p-1] 和 [p+1, high] 写成 [low, p] 或 [p, high]，导致重复排序或跳过 pivot 本身。

• 必须保证 p 在本次调用中已归位，所以左右子区间都不能再包含它
• 递归前要检查区间长度：若 low >= high 直接返回，避免对 0 或 1 个元素调用 partition
• 如果用 Hoare 分区（首尾双向扫描），返回的分界点不一定是 pivot 位置，此时不能直接用它做递归中点，得额外处理

正确调用片段：

void quicksort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quicksort(arr, low, p - 1);   // 左段到 p-1
        quicksort(arr, p + 1, high);   // 右段从 p+1 开始
    }
}

原地排序为什么不能用 vector::swap 而要用 std::swap

vector::swap 是容器级交换，会交换整个堆内存指针和 size/capacity，代价远高于元素值交换；而快排分区里需要的是逐个元素的值交换，用错函数会导致性能暴跌甚至逻辑错乱。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

• std::swap（或 using std::swap; swap(a, b)）才是你想要的值交换
• C++11 后 std::swap 对内置类型是位拷贝，对 int 这类就是 mov 指令，极快
• 如果误写成 arr[i].swap(arr[j])，编译不过；但若定义了自定义类型且重载了 swap 成员函数，则行为取决于实现，不可靠

小数组要不要改用插入排序

快排在小规模数据（比如 high - low ）上不如插入排序，因为递归开销和分支预测失败占比太高。但这不是“建议”，而是实测有效的优化点。

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

• 阈值通常设为 7–16，太小增加判断次数，太大起不到加速作用
• 插入排序必须严格原地：用 for (int i = low + 1; i 循环，内层 <code>while (j > low && arr[j] ，注意 <code>j > low 而非 >= 0，防止越界
• 别在每次递归入口都判断——只在进入 quicksort 时检查一次区间长度即可

加一层判断就生效：

if (high - low < 10) {
    insertion_sort(arr, low, high);
    return;
}

实际写的时候，最常被忽略的是分区函数对退化输入（全相同、已排序、逆序）的鲁棒性，以及递归区间边界的数学一致性——这两处一错，程序要么崩，要么结果错，还很难复现。