手写 partition 函数需用 left < right 循环、移动前检查索引、交换后立即推进指针；快排递归区间为 [low, p-1] 和 [p+1, high]；小数组应切换插入排序，阈值取 7–16。
partition 函数怎么写才不越界
标准库 std::partition 用起来方便，但手写分区逻辑时最容易在边界上出错——尤其是当输入是空容器、单元素、或所有元素都满足/都不满足谓词时。partition 的核心是双指针向中间收缩，但「谁先动」「停在哪」「交换条件」稍有偏差就会访问 arr[-1] 或跳过最后一个有效位置。
- 用
left < right作循环条件，不是<=；否则最后一次迭代后left可能等于right，再自增就溢出 - 内层移动指针前必须先检查索引有效性：比如
while (left < right && arr[left] < pivot)，缺了left < right就可能越界 - 交换后要立刻推进指针（
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<int>::swap 而要用 std::swap
vector::swap 是容器级交换，会交换整个堆内存指针和 size/capacity，代价远高于元素值交换；而快排分区里需要的是逐个元素的值交换，用错函数会导致性能暴跌甚至逻辑错乱。
-
std::swap（或using std::swap; swap(a, b)）才是你想要的值交换 - C++11 后
std::swap对内置类型是位拷贝，对int这类就是 mov 指令，极快 - 如果误写成
arr[i].swap(arr[j])，编译不过；但若定义了自定义类型且重载了swap成员函数，则行为取决于实现，不可靠
小数组要不要改用插入排序
快排在小规模数据（比如 high - low < 10）上不如插入排序，因为递归开销和分支预测失败占比太高。但这不是“建议”，而是实测有效的优化点。
立即学习“C++免费学习笔记（深入）”；
- 阈值通常设为 7–16，太小增加判断次数，太大起不到加速作用
- 插入排序必须严格原地：用
for (int i = low + 1; i <= high; i++)循环，内层while (j > low && arr[j] < arr[j-1])，注意j > low而非>= 0，防止越界 - 别在每次递归入口都判断——只在进入
quicksort时检查一次区间长度即可
加一层判断就生效：
if (high - low < 10) {
insertion_sort(arr, low, high);
return;
}
实际写的时候，最常被忽略的是分区函数对退化输入（全相同、已排序、逆序）的鲁棒性，以及递归区间边界的数学一致性——这两处一错，程序要么崩，要么结果错，还很难复现。
