更新:

2022.12.10

增加分析 6 和分析7, 修整了格式

2023.4.25

调整结构, 修改细节

2023.5.24

增加 python 版代码

算法证明

算法证明使用算法导论里的循环不变式方法

快排模板(以j为分界)

快排属于分治算法，分治算法都有三步：

1. 分成子问题
2. 递归处理子问题
3. 子问题合并

void quick_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    //第二步：递归处理子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);

    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}

待证问题

while 循环结束后，q[l..j] <= x,q[j+1..r] >= x

q[l..j] <= x意为q[l],q[l+1]...q[j-1],q[j]的所有元素都<= x

证明

循环不变式：q[l..i] <= x q[j..r] >= x

1. 初始化

循环开始之前i = l - 1, j = r + 1
则q[l..i],q[j..r]为空，循环不变式显然成立

2. 保持

假设某轮循环开始前循环不变式成立，即q[l..i] <= x, q[j..r] >= x

执行循环体

do i++; while(q[i] < x);
会使得 q[l..i-1] <= x, q[i] >= x

do j--; while(q[j] > x);
会使得 q[j+1..r] >= x, q[j] <= x

if(i < j) swap(q[i], q[j]);
会使得 q[l..i] <= x, q[j..r] >= x

所以，i和j更新之后，下一次循环开始之前，循环不变式依然成立

3. 终止

循环结束时，i >= j

正常情况下，按照循环不变式，我们应该会觉得结果已经显然了

因为i >= j，q[l..i] <= x, q[j..r] >= x

所以按照j来划分的话，q[l..j] <= x, q[j+1..r] >= x是显然的

可是，最后一轮循环有点特殊，因为最后一轮循环的if语句一定不会执行

因为最后一轮循环一定满足 i >= j,不然不会跳出while循环的，所以if语句一定不执行

正确分析：

由于最后一轮的if语句一定不执行

所以，只能保证:

• q[l..i-1] <= x, q[i] >= x

• q[j+1..r] >= x, q[j] <= x

• i >= j

由q[l..i-1] <= x，i >= j(i-1 >= j-1) 和 q[j] <= x 可以得到 q[l..j] <= x

又因为q[j+1..r] >= x
所以，q[l..j] <= x,q[j+1..r] >= x,问题得证

总结:只有最后一轮循环结束时，循环不变式不成立，其余的循环都是成立的
但最终要求的问题还是解决了

注意:循环结束时要记得检查是否存在数组越界/无限划分的情况

所以还需要证明 j 最终的取值范围是[l..r-1](即不存在n划分成0和n的无限划分情况),分析过程在分析5

边界情况分析

快排属于分治算法，最怕的就是 n分成0和n，或 n分成n和0,这会造成无限划分

分析1

以j为划分时，x不能选q[r]

若以i为划分,则x不能选q[l]

假设 x = q[r]

关键句子quick_sort(q, l, j), quick_sort(q, j + 1, r);

由于j的最小值是l,所以q[j+1..r]不会造成无限划分

但q[l..j](即quick_sort(q, l, j))却可能造成无限划分，因为j可能取到r
举例来说，若x选为q[r]，数组中q[l..r-1] < x,

那么这一轮循环结束时i = r, j = r，显然会造成无限划分

分析2

do i++; while(q[i] < x)和do j--; while(q[j] > x) 中不能用q[i] <= x 和 q[j] >= x

假设q[l..r]全相等

则执行完do i++; while(q[i] <= x);之后，i会自增到r+1

然后继续执行q[i] <= x 判断条件，造成数组下标越界(但这貌似不会报错)

并且如果之后的q[i] <= x (此时i > r) 条件也不幸成立，

就会造成一直循环下去(亲身实验)，造成内存超限(Memory Limit Exceeded)

现在已经变成 Time Limit Exceeded 了

分析3

if(i < j) swap(q[i], q[j])能否使用 i <= j

可以使用if(i <= j) swap(q[i], q[j]);

因为 i = j 时，交换一下q[i],q[j] 无影响，因为马上就会跳出循环了

分析4

最后一句能否改用quick_sort(q, l, j-1), quick_sort(q, j, r)作为划分

用i做划分时也是同样的道理

不能

根据之前的证明，最后一轮循环可以得到这些结论

• q[l..i-1] <= x, q[i] >= x
• q[j+1..r] >= x, q[j] <= x
• i >= j

所以，q[l..j-1] <= x 是显然成立的，

但quick_sort(q, j, r)中的q[j] 却是 q[j] <= x，这不符合快排的要求

另外一点，注意quick_sort(q, l, j-1), quick_sort(q, j, r)可能会造成无限划分

当x选为q[l]时会造成无限划分，报错为(MLE),

如果手动改为 x = q[r],可以避免无限划分

但是上面所说的q[j] <= x 的问题依然不能解决，这会造成 WA (Wrong Answer)

分析5

j的取值范围为[l..r-1]

证明:
假设 j 最终的值为 r ,说明只有一轮循环(两轮的话 j 至少会自减两次)

说明q[r] <= x (因为要跳出do-while循环)

说明 i >= r(while循环的结束条件), i 为 r 或 r + 1(必不可能成立)

说明 i 自增到了 r , 说明 q[r] >= x 和 q[l..r-1] < x,

得出 q[r] = x 和 q[l..r-1] < x 的结论,但这与 x = q[l + r >> 1]矛盾

反证法得出 j < r
假设 j 可能小于 l 说明 q[l..r] > x ,矛盾

反证法得出 j >= l
所以 j的取值范围为[l..r-1],不会造成无限划分和数组越界

分析6

while(i < j) 能否改为 while(i <= j)

不能

while(i <= j) 意味着我们认为判断循环结束的条件为 i <= j

那么 if(i < j) 也要改为 if(i <= j)

其实 if(i < j) 改不改都可以, 看完分析 6 后再参考分析 3 可以说明这一点

即

while(i <= j)
{
    do i++; while(q[i] < x);
    do j--; while(q[j] > x);
    if(i <= j) swap(q[i], q[j]);
}

参考循环不变式的证明, 只有最后一轮循环有所不同

我们可以得到:

• q[l..i-1] <= x, q[i] >= x

• q[j+1..r] >= x, q[j] <= x

• i > j

最终, 我们还能证明出 q[l..j] <= x,q[j+1..r] >= x

也就是说, while(i <= j) 并不会改变循环不变式的部分

但修改后的代码提交后却是 Time Limit Exceeded(TLE), 原因在于无限划分

$~$

具体来说, 就是 j 在某些情况下能取到 l-1, 此时就是无限划分

q[l..r] 划分为 q[l..l-1], q[l..r]

某些情况指: 数组只有两个元素 [a, b] 且 a < b

这种情况下,

初始 i = l - 1, j = r + 1

第一轮 while 循环结束 i = l, j = l

第二轮 while 循环结束 i = r, j = l-1

于是 while(i <= j) 就造成了无限划分, 而 while(i < j) 就不会造成这个问题, 因为第一轮 while 循环结束后就跳出去了

所以, 不能用 while(i <= j)

$~$

有些人可能会疑惑: 这种情况看起来比较极端啊, 如果构造数组 [3, 2, 1] 会不会就不会遇到这种情况了

其实不然, 因为快排是分治算法, 往下递归时总会遇到 [a, b], a < b 这种情况

只要有一个这种情况, 就会进入无限划分出不来.

只有在数组元素全相等情况下才遇不到这种情况, 此时算法就能正常运行了, 读者可自行验证

分析7

循环不变式证明过程中

do i++; while(q[i] < x);
会使得 q[l..i-1] <= x, q[i] >= x

会使得 q[l..i-1] <= x, q[i] >= x 能否改为 会使得 q[l..i-1] < x, q[i] >= x

不能

这里的 q[l..i-1] <= x 是配合循环不变式 q[l..i] <= x q[j..r] >= x 的

于是问题就变成了循环不变式中 q[l..i] <= x 能否改为 q[l..i] < x

假定循环不变式是 q[l..i] < x, q[j..r] > x

执行两个 do-while 循环

do i++; while(q[i] < x);
会使得 q[l..i-1] < x, q[i] >= x

do j--; while(q[j] > x);
会使得 q[j+1..r] > x, q[j] <= x

则执行 if 语句后

if(i < j) swap(q[i], q[j]);

就会变成 q[l..i] <= x, q[j..r] >= x, 与假设矛盾

所以, 考虑最全面的描述还是要带上 = 的

分析8

使用 do-while 循环的好处

好处在于循环变量 i和j 一定更新, 循环不会卡死

如果使用while循环, i和j 在特殊情况下不更新的话,循环就会卡死

例:

while(q[i] < x) i++;
while(q[j] > x) j--;
当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环

其余模板

用i做划分时的模板

// 从小到大
void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r + 1 >> 1];//注意是向上取整,因为向下取整可能使得x取到q[l]
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, i - 1), quick_sort(q, i, r);//不用q[l..i],q[i+1..r]划分的道理和分析4中j的情况一样
}

// 从大到小(只改两个判断符号)
void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] > x); // 这里和下面
        do j--; while(q[j] < x); // 这行的判断条件改一下
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

python版

def quick_sort(q, l, r):
    if l >= r:
        return

    i = l - 1
    j = r + 1
    x = q[l + r >> 1]

    while i < j:
        i += 1
        while q[i] < x:
            i += 1

        j -= 1
        while q[j] > x:
            j -= 1

        if i < j:
            q[i], q[j] = q[j], q[i]

    quick_sort(q, l, j)
    quick_sort(q, j + 1, r)


n = int(input())
q = list(map(int, input().split()))

quick_sort(q, 0, n - 1)

print(' '.join(list(map(str, q))))

总结快排思路

1. 有数组 q, 左端点 l, 右端点r

2. 确定划分边界 x

3. 将 q 分为 <=x 和 >=x 的两个小数组

4. $i$ 的含义: $i$ 之前的元素都 $\leq x$, 即 $q[l..i-1]$ $\leq x$

5. $j$ 的含义: $j$ 之后的元素都 $\geq x$, 即 $q[j+1..r]$ $\geq x$

6. 结论: $while$ 循环结束后, $q[l..j]$ $\leq x,q[j+1..r]$ $\geq x$

7. 简单不严谨证明:

   $while$ 循环结束时, $i \geq j$

   若 $i > j$ , 显然成立

   若 $i = j$

   $\because$ 最后一轮循环中两个 $do-while$ 循环条件都不成立

   $\therefore$ $q[i] \geq x, q[j] \leq x$

   $\therefore$ $q[i] = q[j] = x$

   $\therefore$ 结论成立

8. 递归处理两个小数组