QQ截图20210516105844.png
快排属于分治算法，分治算法都有以下几个步骤。

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

快排的步骤分为:

1.确定基准值 x ,可取随机一个元素
2.调整区间,使得 [l,x]<=x** , **[x,r]>=x
3.递归处理左右区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort(int q[], int l, int r)
{
    //递归的终止情况(合法情况l==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循环结束后 [l,j]<=x,[j+1,r]>x
循环不变式:

q[l..i] <= x q[j..r] >= x

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

2.某轮循环开始前(循环不变式成立) 执行代码

1
2
3
4
5
6
7
8
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

照上面的逻辑，下一次循环开始之前，不变式依然成立

3.循环终止

循环结束时, i>=j,q[l..i]<=x,q[j..r]>=x
按照j来划分, 可以得到 q[l..j] <=x,q[j+1..r]>=x

如何证明这个结论是正确的呢,关键在于最后一轮循环
因为i>=j,所以swap操作并不会进行,即我们只能保证
p[l,i-1]<=x,p[i]>=x,p[j+1,r]>=x,p[j]<=x**
因为 **p[l,i-1]<=x,i>=j(i-1>=j-1) 以及 p[j]<=x** 可以得到 **p[l,j]<=x**
又因为 **p[j+1,r]>=x (上面的证明) ，所以问题得证