作者yauhh (喲)
看板Programming
標題Re: [問題] Costed Sorting 的演算法
時間Sat Nov 13 10:52:08 2010
※ 引述《ericinttu (腿力爆增 XD)》之銘言：
: (b) 可利用數字特別小的來當作swap助手. (如你後面這的例子)
: 從 (a) 的觀點出發的話
: cost value
: 1 8 9 7 6 0
: 1 8 6 7 9 0 + 6 + 9 = 15
: 1 7 6 8 9 15+ 7 + 8 = 30
: 1 6 7 8 9 30+ 6 + 7 = 43
: 從 (b) 的觀點出發的話, 也就是數字定位之前都先用1放在該位置.
看起來處理方法是:
1. 先定位處理範圍,例如 18976 目標是 16789, 只要調整 8976 部份即可.
2. 取原列中最小值 1 ,與調整範圍的最小值 6 互換 (耗7); 原本 1 位置記為
特殊位置.
3. 最小值 1 站在什麼位置,就和目標值互換位置,換了位置之後將較大值的位置
從處理範圍排除,所以
68971 先換 1 9 (耗10)
得 68179 ,換 1 7 (耗8)
得 68719 ,換 1 8 (耗9)
得 61789
到此已經把調整範圍的數字換完了. 最後處理範圍只剩下 1 的位置.
4. 把特殊位置的 6 和調整範圍的最小值 1 互換位置, (耗7) 得 16789,
總共交換成本為 7+10+8+9+7 = 41.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.208.226