共计 3220 个字符,预计需要花费 9 分钟才能阅读完成。
这篇文章写于我刚学算法时。好家伙,第一道题快排就卡我老半天。然而好消息是,我算是没有得过且过,花了一早晨和一上午,把所有状况都捋了一遍、把迭代过程思考分明了。之后便感觉入了门,有了感觉,后续其余题目都没有卡我这么久过。
被很简略的快排 代码运行状态:Memory Limit Exceeded
老半天。
最初推敲半天越界这事儿。总结起来一句话:避免出现 func(l, r) {... func(l, r) ... }
(递归时传递到下一层的边界值不放大)这种状况,因为这是死循环。 如何防止?比方 func(l, r) {func(l, j), func(j + 1, r)}
中,j
至多满足 j > r
(j
从 r
身上来到,避免 func(l, j) 是 func(l, r)
),就可用。
#include <iostream>
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 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);
}
int main() { 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; }
手贱,非得写成:
quick_sort(q, l, i - 1), quick_sort(q, i, r);
好家伙,报错。半天没看进去,起初才豁然开朗,你要是用 i
分界,下面得是 x = q[l + r + 1 >> 1];
。
那我上面这样不行吗?
x = q[l+r >> 1];
...
quick_sort(q, l, j - 1), quick_sort(q, j, r);
// 或者这样不行吗?x = q[l+r >> 1];
...
quick_sort(q, l, i - 1), quick_sort(q, i, r);
// 或者这样不行吗?x = q[l+r >> 1];
...
quick_sort(q, l, i), quick_sort(q, i + 1, r);
// 或者这样不行吗?x = q[l+r+1 >> 1];
...
quick_sort(q, l, j), quick_sort(q, j + 1, r);
// 或者这样不行吗?x = q[l+r+1 >> 1];
...
quick_sort(q, l, j - 1), quick_sort(q, j, r);
// 或者这样不行吗?x = q[l+r+1 >> 1];
...
quick_sort(q, l, i), quick_sort(q, i + 1, r);
上述都不行,看我一一举反例。
咱们输出长度是 2
的数组,则第一层循环:l = 0, r = 1
(即 quick_sort(0, 1)
),如果进入第二层循环时,还呈现 quick_sort(0, 1)
的状况,则陷入死循环。
下表中,“传到函数的
i, j
”指调用quick_sort(q, l, ?i/j), quick_sort(q, ?i/j, r)
中i, j
的值。下表中,最初一列标记
x
示意将使程序陷入死循环。
对于 int mid = l+r >> 1;
:
测试用例 | q[mid] |
传到函数的i, j |
传入参数 |
---|---|---|---|
0 1 |
0 | 0, 0 |
j-1 j => (0, -1), (0, 1)x |
0 1 |
0 | 0, 0 |
i-1 i => (0, -1), (0, 1)x |
0 1 |
0 | 0, 0 |
j j+1 => (0, 0), (1, 1) √ |
1 0 |
1 | 1, 0 |
i i+1 => (0, 1)x, (2, 1) |
1 0 |
1 | 1, 0 |
j j+1 => (0, 0), (1, 1) √ |
可见,在 int mid = l+r >> 1;
时,四种组合中只有 j j+1
禁受住了 0 1
和 1 0
的双重考验。
对于 int mid = l+r+1 >> 1;
:
测试用例 | q[mid] |
传到函数的i, j |
传入参数 |
---|---|---|---|
1 0 |
0 | 1, 0 |
j-1 j => (0, -1), (0, 1)x |
1 0 |
0 | 1, 0 |
i i+1 => (0, 1)x, (2, 1) |
1 0 |
0 | 1, 0 |
i-1 i => (0, 0), (1, 1) √ |
0 1 |
1 | 1, 1 |
j j+1 => (0, 1)x, (2, 1) |
0 1 |
1 | 1, 1 |
i-1 i => (0, 0), (1, 1) √ |
可见,在 int mid = l+r+1 >> 1;
时,四种组合中只有 i-1 i
禁受住了 0 1
和 1 0
的双重考验。
这是为什么呢?
- 这里有相干证实:AcWing 785. 疾速排序算法的证实与边界剖析
- 如果你没急躁看上述较为谨严的证实,能够看文末我写的
我用比拟笨的办法了解是:
int mid = l+r >> 1;
:则可证实j
的取值范畴是[l, r-1]
,因而对于边界组合j j+1
有quick_sort(q, l, j 小于 r), quick_sort(q, j+ 1 大于 l, r)
,永远都不会有quick_sort(q, l, r)
呈现。int mid = l+r+1 >> 1;
:则可证实i
的取值范畴是[l+1, r]
,因而对于边界组合i-1 i
有quick_sort(q, l, i- 1 小于 r), quick_sort(q, i 大于 l, r)
,永远都不会有quick_sort(q, l, r)
呈现。
OK,那上面就是背诵:
- 快排中,
int mid = l+r >> 1;
(mid
向下取整),是j j+1
,因为j
取值范畴是[l r-1]
- 我集体是不太喜爱背诵的,还是晓得原理,感觉到时候能够疾速推导进去靠谱,推导如下。
用较清晰然而蠢笨的办法证实一下 mid
向下取整时 j
属于 [l, r-1]
。
向下取整时 j
属于 [l, r-1]
== 等价于 == 向下取整时至多有两次 j--
被执行
上面分三种非凡状况探讨(一般状况不探讨),能够看出三种状况中都至多有两次 j--
被执行
状况 1:j
在 r
处就不再 q[j] > x
,而i
在l
处还满足q[i] < x
q[mid] x
9 8
begin i j
step1 i j do i++; while(q[i] < x);
step2 i j do j--; while(q[j] > x);
step3 8 9
step4 i j swap(q[i], q[j]);
step5 ij do i++; while(q[i] < x);
step6 j i do j--; while(q[j] > x);
跳出循环 while(i < j) {}
j
在 r
处就不再 q[j] > x
,而i
在l
处还满足q[i] < x
;因而对于l < r
,还要再跳一轮,因为是 do while
而不是 while do
,所以不论 i
或 j
什么条件,都得再至多来一次 i++; j--;
。
状况 2:j
在 r
处还满足 q[j] > x
,而i
在l
处就不再q[i] < x
q[mid] x
8 9
begin i j
step1 i j do i++; while(q[i] < x);
step2 ij do j--; while(q[j] > x);
step3 8 9
跳出循环 while(i < j) {}
j
在 r
处还满足 q[j] > x
,因而,肯定会继续执行j--
,j
肯定会小于r
。
状况 3:j
在 r
处就不再 q[j] > x
,且i
在l
处就不再q[i] < x
q[mid] x
8 8
begin i j
step1 i j do i++; while(q[i] < x);
step2 i j do j--; while(q[j] > x);
step3 8 8
step4 i j swap(q[i], q[j]);
step5 ij do i++; while(q[i] < x);
step6 j i do j--; while(q[j] > x);
跳出循环 while(i < j) {}
j
在 r
处就不再 q[j] > x
,且i
在l
处就不再q[i] < x
;此时有 i < j
,因而不跳出循环,执行 swap
;对于l < r
,还要再跳一轮,因为是 do while
而不是 while do
,所以不论 i
或 j
什么条件,都得再至多来一次 i++; j--;
。
这里的魅力在于 do while
:不论咋的,你满不满足条件,我先给你挪动一下,你再判断。
对于二分法,核心思想也是避免出现func(l, r) {func(l, r); }
,因而呈现 mid = l + r >> 1;
则必有 r = mid;
,因为 mid
是向下取整,l < r
时 mid
必定碰不到 r
。
我是小拍,记得关注给个在看!