雙路快排Partition break的問題(i>j)
来源：3-7 双路快速排序法
阿寶1118
2021-07-29
老師，關於雙路快排中，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同一個元素是多餘的)?
1回答
-
你的模拟应该是有问题的。
因为 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 大，但在这个数组中，为空。
你可以将代码的随机化取消掉，就使用第一个元素作为标定点，用这个测试用例，实际运行，单步跟踪，看一下每一步程序中的各个变量的值是怎样的？
继续加油！：）
012021-07-29
相似问题