雙路快排Partition break的問題(i>j)

Question

老師，關於雙路快排中，Partition的程式碼我有點小疑惑
就是在while退出迴圈的條件
if(i>j)這個條件，正常的亂序陣列，邏輯是正確的
但是如果出現以下這種場景

要Partition的陣列為
arr 0 1 2 3 4 5
9 1 2 4 5 6
則依照程式碼的邏輯(第一行為array index 第二行為value)
Round1
0 1 2 3 4 5
9 4 6 2 1 5 i指向arr[1],j指向arr[5]
Round2
0 1 2 3 4 5 i指向arr[5],j指向arr[5]
9 4 6 2 1 5
做完swap後—>i++,j–
0 1 2 3 4 5 i指向arr[6]—>空,j指向arr[4]
9 4 6 2 1 5

那麼依照依照老師您課程中的邏輯
此時會將arr[0]與arr[4]交換
陣列會變成
0 1 2 3 4 5
1 4 6 2 9 5
這樣陣列的左半部的確從arr[0]~arr[3]都是小於等於v
但是右半部明顯不大於等於v耶?(5!>9)
這樣做再多次的左右半邊Partition
5永遠都會在9的右邊(錯誤排序)

請問老師 在這種情況下，這樣的算法到最後卻還是能排好序呢?

還有另一個問題
讓if(i>=j)應該也是沒問題的(因為陣列已經完全被訪問過—>swap同一個元素是多餘的)?

Answer 1

liuyubobobo 2021-07-29 11:55:10

你的模拟应该是有问题的。

因为 9 后面的所有数字都比 9 小，所以第一轮以后，i 将指向 6（即越界），而不是停在 5 的位置。而 j 停在 5。所以 i > j，循环直接结束了。

然后，9 会和 arr[j] 即 arr[5] 即 5 交换。变成 5 4 6 2 1 9。9 的前面都比 9 小；9 的后面比 9 大，但在这个数组中，为空。

你可以将代码的随机化取消掉，就使用第一个元素作为标定点，用这个测试用例，实际运行，单步跟踪，看一下每一步程序中的各个变量的值是怎样的？

继续加油！：）

• 提问者 阿寶1118 #1

  是的!老師我知道我自己模擬的問題在哪了!
  索引值i會越界而不是標記在最後一個元素
  我知道問題點在哪了，謝謝您的指點!