Re: [問題] quicksort swap pivot時出現問題
要把 pivot 放中間也是可以唷, 不過這要引入視圖(view) 的概念.
簡單說就是提供一個抽象化層, 讓我們看到的陣列不是實際上的陣
列, 而這個抽象化的目的是讓我們看不到 pivot, 如此就可以解決
partition 時會把 pivot 搬來搬去的問題
┌──┬──┬──┬──┐
視圖 │ 3 │ 4 │ 2 │ 5 │
└──┴──┴──┴──┘
┌──┬──┬──┬──┬──┐
陣列 │ 3 │ 4 │ 1 │ 2 │ 5 │
└──┴──┴──┴──┴──┘
(pivot)
在提供這層抽象化前, 首先得面對的問題就是索引轉換. 由上圖可
以看到元素 5 在視圖裡的索引是 3, 但在陣列裡的索引卻是 4,
不過這個轉換並不會太複雜
另外在 partition 的最後, 要稍微注意 pivot 擺放的位置, 其他
就沒什麼特別的地方. 實作可以參考下面的範例
無抽象化: https://bit.ly/2X13mEN
有抽象化: https://bit.ly/2IaFVWt
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.176.51.8
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1555011335.A.919.html
※ 編輯: poyenc (180.176.51.8), 04/12/2019 03:38:55
推
04/17 21:24,
6年前
, 1F
04/17 21:24, 1F
討論串 (同標題文章)