→ stanleyqoo:經過私下討論後 終於大功告成 謝謝麥爺! 推 218.175.25.35 12/30
※ 引述《stanleyqoo ( ★恆星的恆心☆ )》之銘言：
: : In-Place qsort跟一般qsort一樣或類似嗎??
: : 我學資結時沒見過In-Place的...
: 不一樣唷 但是可以說類似吧
: 我把部分的 In-Place Quick Sort 的跑的片段拿上來給你看
: 85 24 63 45 17 31 96 [50]
: <l> <r>
: 85 24 63 45 17 31 96 [50]
: <l> <r>
: 31 24 63 45 17 85 96 [50]
: <l> <r>
: 31 24 63 45 17 85 96 [50]
: <l> <r>
: 31 24 17 45 63 85 96 [50]
: <l> <r>
: 31 24 17 45 63 85 96 [50]
: <r> <l>
: 31 24 17 45 [50] 85 96 63
: <r> <l>
: 用 [ ] 框起來的是 PIVOT
: 然後各別從左邊和右邊攻過去 我老師都愛用"攻"這個字
: (1)由左攻 攻至比PIVOT大時停止 標記<l>
: (2) 右 PIVOT小 停止 標記<r>
: (3)交換此時左右兩個標記的值
: (4)若 <l> 和 <r> 交錯時 就把PIVOT 和 <l> 交換
: 上面的片段就是用這個方法去執行
: 我們老師要我們接著做下去 做到全部SORT完為止
: 但是我卻不知道是不是一定要選最右邊的當PIVOT
: 還是任意去選都可以
我大概懂了..
選最右邊當PIVOT是便於使用的關係吧
如果我選了31
85 24 63 45 17 [31] 96 50
<l> <r>
17 24 63 45 85 [31] 96 50
<r> <l>
17 24 [31] 45 85 63 96 50
<r> <l>
到這邊應該要用遞迴把[31]左邊跟右邊重新sort吧?
這樣看來隨便挑都是可以的
但是從遞迴使用的觀點上來看挑選最邊邊(左或右)的element來當PIVOT應當是最好的選擇
便於撰寫，減少判斷元素個數，閱讀方便
嗯嗯
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.221.134