原始题目

下面这段代码横线处应该填什么？

int partition(int a[], int left, int right) {
    int pivot = a[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    ___;
    return i + 1;
}

答案：swap(a[i + 1], a[right])

完整写法（Lomuto 划分，算法导论版）：

int partition(int a[], int left, int right) {
    int pivot = a[right];          // 取最右元素为基准
    int i = left - 1;              // i 指向“小于等于区间”的末尾
    for (int j = left; j < right; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a[i], a[j]);      // 把小的换到左边
        }
    }
    swap(a[i + 1], a[right]);      // 把 pivot 换到分界点
    return i + 1;                  // pivot 的最终下标
}

为什么是 i+1 而不是 i

循环结束时，数组被切成三段（这是整个 partition 的不变量）：

• [left, i]：全部 ≤ pivot
• [i+1, right-1]：全部 > pivot
• a[right]：pivot 本身

所以 pivot 的正确落点就是 i + 1——把它换过去，左边都比它小、右边都比它大，返回 i + 1 作为分割点。

填 swap(a[i], a[right]) 是最常见的 off-by-one 错误：会把一个本该留在左边的元素换到末尾，划分直接失效。

图解（pivot = 5，i = 3）

注意最后的交换是 6 和 5 对调：pivot 落到下标 4，而原来那个大于 pivot 的 6 被换到了末尾——它现在在右半边，位置是对的（只是没排好序，交给递归处理）。

配套调用：p 不能参与递归

void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);      // 左边
    quickSort(a, p + 1, r);      // 右边
}

p 这个位置已经排好，必须跳过。如果写成 quickSort(a, l, p)，遇到大量重复元素时会无限递归（区间不缩小）。

三个延伸考点

1. <= 还是 <：本题用 <=，等于 pivot 的元素全部归到左边。数组元素全相等时，每次划分都极不平衡，快排退化成 \(O(n^2)\)。这也是三路快排（把 =pivot 的单独成一段）存在的理由。
2. 不稳定：Lomuto 划分中的交换会打乱相同元素的相对顺序，所以快排不是稳定排序（stable_sort 用的是归并）。
3. pivot 取最右的隐患：对已排序数组，每次 pivot 都是最大值，同样退化成 \(O(n^2)\)。实际工程里常用随机取 pivot 或三数取中。

复杂度

考点总结（CSP-J/S 初赛、程序填空题）

1. 程序填空见到 i = left - 1 + swap(a[i], a[j]) → Lomuto 划分，空行填 swap(a[i+1], a[right])。
2. 返回值一定是 i + 1，且与上一行的交换下标一致。
3. 递归时 p 的位置跳过：quickSort(l, p-1) 和 quickSort(p+1, r)。
4. 记不变量：[left, i] ≤ pivot，[i+1, right-1] > pivot。

思考题

如果把 if (a[j] <= pivot) 改成 if (a[j] < pivot)，划分结果会有什么变化？