[問題] 演算法問題

看板Prob_Solve作者 (可愛小孩子)時間9年前 (2014/10/03 08:54), 編輯推噓7(7推 0噓 5→)
留言12則, 6人參與, 最新討論串5/8 (看更多)
給一字串全由字母 A-Z 組成 將其依字母順序由小到大排序 限定只能相鄰字母兩兩交換 問至少要交換幾次 能排序完成 Ex. Input : DCBA Output: 6 請問這有好的算法嗎 謝謝 :) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.233.210 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1412297667.A.454.html
推
10/03 09:06, , 1F
從merge sort下手
10/03 09:06, 1F
推
10/03 09:19, , 2F
所求為逆序對的數目, 不過基本上就是 merge sort...
10/03 09:19, 2F
→
10/03 09:36, , 3F
謝謝 c 大 和 L 大
10/03 09:36, 3F
→
10/03 09:39, , 4F
L 大好厲害，可以想到是求「逆序對」數目，讚歎！
10/03 09:39, 4F
推
10/03 20:06, , 5F
merge sort 可以做到「只能相鄰字母交換」嗎？
10/03 20:06, 5F
→
10/03 20:07, , 6F
感覺上好像 bubble sort 與 inersetion sort 可以。
10/03 20:07, 6F
→
10/03 20:08, , 7F
抱歉，打錯字，insertion sort。
10/03 20:08, 7F
推
10/04 01:31, , 8F
用什麼sort都可以,只是merge sort能O(nlgn)算逆序數
10/04 01:31, 8F
推
10/04 14:07, , 9F
那為什麼不用counting sort? 聽起來更快
10/04 14:07, 9F
推
10/04 14:12, , 10F
springman: merge sort不能做到相鄰字母交換 但是改一改之後
10/04 14:12, 10F
→
10/04 14:13, , 11F
可以用來數逆序對
10/04 14:13, 11F
推
10/04 20:10, , 12F
說得也是，只是要計算交換幾次而已，謝謝。
10/04 20:10, 12F
‣ 更多 cutekid 的文章
文章代碼(AID): #1KBVF3HK (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 5 之 8 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共8篇)
‣ 更多 cutekid 的文章
文章代碼(AID): #1KBVF3HK (Prob_Solve)