关于算法:又被分治题卡住好几个小时用最笨的方法搞懂分治法边界告别死循环

这篇文章写于我刚学算法时。好家伙，第一道题快排就卡我老半天。然而好消息是，我算是没有得过且过，花了一早晨和一上午，把所有状况都捋了一遍、把迭代过程思考分明了。之后便感觉入了门，有了感觉，后续其余题目都没有卡我这么久过。

被很简略的快排 代码运行状态：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;：

可见，在 int mid = l+r >> 1; 时，四种组合中只有 j j+1 禁受住了 0 1 和 1 0 的双重考验。

对于 int mid = l+r+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。

我是小拍，记得关注给个在看！