[問題] 演算法問題

[cutekid (可愛小孩子)]

給一字串全由字母 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
推 ckc1ark: 從merge sort下手
推 LPH66: 所求為逆序對的數目, 不過基本上就是 merge sort...
→ cutekid: 謝謝 c 大 和 L 大
→ cutekid: L 大好厲害，可以想到是求「逆序對」數目，讚歎！
推 springman: merge sort 可以做到「只能相鄰字母交換」嗎？
→ springman: 感覺上好像 bubble sort 與 inersetion sort 可以。
→ springman: 抱歉，打錯字，insertion sort。
推 johnathan717: 用什麼sort都可以,只是merge sort能O(nlgn)算逆序數
推 DJWS: 那為什麼不用counting sort? 聽起來更快
推 DJWS: springman: merge sort不能做到相鄰字母交換 但是改一改之後
→ DJWS: 可以用來數逆序對
推 springman: 說得也是，只是要計算交換幾次而已，謝謝。