快速排序模板
快速排序算法的证明与边界分析
算法证明
算法证明使用算法导论里的循环不变式方法
快排模板(以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);
//第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤
}
复制代码
待证问题
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
- 初始化
循环开始之前i = l - 1, j = r + 1
则q[l..i],q[j..r]
为空,循环不变式显然成立
- 保持
假设某轮循环开始前循环不变式成立,即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更新之后,下一次循环开始之前,循环不变式依然成立
注意:由于使用do-while循环,所以i
和j
一定会!!!自增!!!,使得循环会继续下去,但是如果采用while循环(i
和j
的初始化做出对应的变更),i
和j
在特殊情况下不自增的话,循环就会卡死
例如:
while(q[i] < x) i++;
while(q[j] > x) j--;
当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环
复制代码
-
终止
循环结束时,
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语句一定不执行
所以,只能保证
i >= j
和q[l..i-1] <= x, q[i] >= x
和q[j+1..r] >= x, q[j] <= x
由
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
,这会造成无限划分
- 以
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
,显然会造成无限划分
-
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)
-
if(i < j) swap(q[i], q[j])
能否使用i <= j
可以使用
if(i <= j) swap(q[i], q[j]);
因为
i = j
时,交换一下q[i],q[j]
无影响,因为马上就会跳出循环了 -
最后一句能否改用
quick_sort(q, l, j-1), quick_sort(q, j, r)
作为划分(用i
做划分时也是同样的道理,)不能
根据之前的证明,最后一轮循环可以得到这些结论
j <= i
和q[l..i-1] <= x, q[i] >= x
和q[j+1..r] >= x, q[j] <= x
所以,
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)
-
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]
,不会造成无限划分和数组越界
-
while
循环的结束条件能不能改成i <= j
顺带一提用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的情况一样
}
#include<bits/stdc++.h> //万能头文件
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r) {
if (l >= r) {
return;
}
int x = q[l];
int i = l - 1;
int j = 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);
}
int main() {
//scanf的输入要比cin的输入快
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", q[i]);
return 0;
}