作者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