推 chemical1223:所以說要看程式怎麼寫嗎@@? 06/10 04:46
※ 引述《chemical1223 (康康康康康康)》之銘言：
: 想請問的是開始移動後若i跟j同時停留在同一個數上該怎麼解決？
: 例如以下問題
: 給定 26,5,37,1,61,11,59,15,27，用QuickSort排列
: 第一次執行完會是
: 11,5,15,1,26,61,59,37,27
: 左半部沒問題
: 我想討論的是26的右半部 61,59,37,27
: 執行完後發現會有下面結果
: 61 , 59 , 37 , 27
: ij (i,j都停在27上)
: 此時swap i跟j
: 61 , 59 , 37 , 27
: ij
: j繼續前進
: 61 , 59 , 37 , 27
: j i
: 此時i、j交錯，swap j跟pivot
: 得 37,59,61,27
: 其實在上一步我就知道自己錯了，可是我不知道自己錯在哪裡
: 跟pivot置換的不是交錯後j所指的那個數嗎？翻書也看不出個所以然來
: 想請問板友們遇到這種情況要怎麼辦？
: 若有資訊不足的地方麻煩提醒，我會再補上
: 謝謝各位
依照你做題方式，你的pivot應該是61了
61的話，最後i跟j會停在27，SWAP 61跟27，變27 59 37 61(61不加入下次排序)
然後pivot變27，i跟j停在59，但27比59小，所以不會SWAP，剩下59 37
最後pivot變59，.....(中略)，SWAP 59跟37，之後判斷排序結束
其實要看程式寫法...參考這篇http://0rz.tw/a122P
裡面的C的寫法比較OK，不是判斷ij是否交錯，而是判斷i是否<j(因為會有i=j)
雖然也不很OK啦
總之如果有給定程式碼或虛擬碼就照著做比較好
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.92.133