[[406991]]

這篇文章寫于我剛學(xué)算法時(shí)。好家伙，第一道題快排就卡我老半天。但是好消息是，我算是沒有得過且過，花了一晚上和一上午，把所有情況都捋了一遍、把迭代過程考慮清楚了。之后便感覺入了門，有了感覺，后續(xù)其他題目都沒有卡我這么久過。

被很簡單的快排 代碼運(yùn)行狀態(tài)：Memory Limit Exceeded 老半天。

最后琢磨半天越界這事兒?？偨Y(jié)起來一句話：避免出現(xiàn) func(l, r) { ... func(l, r) ... } (遞歸時(shí)傳遞到下一層的邊界值不縮小)這種情況，因?yàn)檫@是死循環(huán)。 如何避免?比如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); 

好家伙，報(bào)錯(cuò)。半天沒看出來，后來才恍然大悟，你要是用 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的數(shù)組，則第一層循環(huán)：l = 0, r = 1(即 quick_sort(0, 1))，如果進(jìn)入第二層循環(huán)時(shí)，還出現(xiàn) quick_sort(0, 1)的情況，則陷入死循環(huán)。

下表中，“傳到函數(shù)的i, j”指調(diào)用 quick_sort(q, l, ?i/j), quick_sort(q, ?i/j, r) 中 i, j 的值。

下表中，最后一列標(biāo)記 x 表示將使程序陷入死循環(huán)。

對于 int mid = l+r >> 1;：

可見，在 int mid = l+r >> 1; 時(shí)，四種組合中只有 j j+1 經(jīng)受住了 0 1 和 1 0 的雙重考驗(yàn)。

對于 int mid = l+r+1 >> 1;：

可見，在 int mid = l+r+1 >> 1; 時(shí)，四種組合中只有 i-1 i 經(jīng)受住了 0 1 和 1 0 的雙重考驗(yàn)。

這是為什么呢?

• 這里有相關(guān)證明：AcWing 785. 快速排序算法的證明與邊界分析[1]
• 如果你沒耐心看上述較為嚴(yán)謹(jǐn)?shù)淖C明，可以看文末我寫的

我用比較笨的方法理解是：

• 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) ，永遠(yuǎn)都不會(huì)有 quick_sort(q, l, r) 出現(xiàn)。
• 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) ，永遠(yuǎn)都不會(huì)有 quick_sort(q, l, r) 出現(xiàn)。

OK，那下面就是背誦：

• 快排中，int mid = l+r >> 1;( mid 向下取整)，是 j j+1，因?yàn)閖 取值范圍是 [l r-1]
• 我個(gè)人是不太喜歡背誦的，還是知道原理，覺得到時(shí)候可以快速推導(dǎo)出來靠譜，推導(dǎo)如下。

用較清晰但是笨拙的方法證明一下 mid 向下取整時(shí) j 屬于 [l, r-1]。

向下取整時(shí) j 屬于 [l, r-1] ==等價(jià)于== 向下取整時(shí)至少有兩次 j-- 被執(zhí)行

下面分三種特殊情況討論(普通情況不討論)，可以看出三種情況中都至少有兩次 j-- 被執(zhí)行

情況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); 
跳出循環(huán) while(i < j) {} 

j在r處就不再q[j] > x，而i在l處還滿足q[i] < x;因此對于l < r，還要再跳一輪，因?yàn)槭?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 
跳出循環(huán) while(i < j) {} 

j在r處還滿足q[j] > x，因此，一定會(huì)繼續(xù)執(zhí)行j--，j一定會(huì)小于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); 
跳出循環(huán) while(i < j) {} 

j在r處就不再q[j] > x，且i在l處就不再q[i] < x;此時(shí)有 i < j ，因此不跳出循環(huán)，執(zhí)行 swap;對于l < r，還要再跳一輪，因?yàn)槭?do while 而不是 while do ，所以不管 i 或 j 什么條件，都得再至少來一次 i++; j--; 。

這里的魅力在于 do while ：不管咋的，你滿不滿足條件，我先給你移動(dòng)一下，你再判斷。

對于二分法，核心思想也是避免出現(xiàn)func(l, r) { func(l, r); } ，因此出現(xiàn) mid = l + r >> 1; 則必有 r = mid; ，因?yàn)?mid 是向下取整，l < r 時(shí) mid 肯定碰不到 r 。