作者ray02825 (麵包)
看板Grad-ProbAsk
標題[理工] [資結]-quick sort
時間Tue Oct 27 21:39:31 2009
quick sort的演算法問題
假設現在是sort A[l]--A[u]
它一開始把i設成l j設成u+1 pivot key設成A[l].key
然後就讓i++去找比A[l].key大的值
但是如果A[l].key就是最大值了
這個演算法不就沒辦法跑？
因為找不到比A[l].key還要大的值就卡在i的loop內
請問各位大大這應該怎麼做？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.125.162.59
推 abien:i加到u還是沒找到就會跳離loop啦 10/27 22:12
推 polomoss:如果A[1]是最大的話，右邊每個值都比他小，則A[1]的值 10/27 22:53
→ polomoss:會被換到最右邊，然後這回合就結束，左邊繼續recursive 10/27 22:54
→ polomoss:喔，懂你的問題，通常左右各會有個∞，所以會中址在最後 10/27 22:56
推 gsrr:最後面放一個 比所有數都大的值. 10/27 23:19
→ ray02825:感謝3位的解答 瞭解了 10/28 10:26