作者cutekid (可愛小孩子)
看板Prob_Solve
標題[問題] 演算法問題
時間Fri Oct 3 08:54:24 2014
給一字串全由字母 A-Z 組成
將其依字母順序由小到大排序
限定只能
相鄰字母兩兩交換
問至少要交換幾次
能排序完成
Ex.
Input : DCBA
Output: 6
請問這有好的算法嗎
謝謝 :)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.233.210
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1412297667.A.454.html
1F：推 ckc1ark: 從merge sort下手 10/03 09:06
2F：推 LPH66: 所求為逆序對的數目, 不過基本上就是 merge sort... 10/03 09:19
3F：→ cutekid: 謝謝 c 大 和 L 大 10/03 09:36
4F：→ cutekid: L 大好厲害，可以想到是求「逆序對」數目，讚歎！ 10/03 09:39
5F：推 springman: merge sort 可以做到「只能相鄰字母交換」嗎？ 10/03 20:06
6F：→ springman: 感覺上好像 bubble sort 與 inersetion sort 可以。 10/03 20:07
7F：→ springman: 抱歉，打錯字，insertion sort。 10/03 20:08
8F：推 johnathan717: 用什麼sort都可以,只是merge sort能O(nlgn)算逆序數 10/04 01:31
9F：推 DJWS: 那為什麼不用counting sort? 聽起來更快 10/04 14:07
10F：推 DJWS: springman: merge sort不能做到相鄰字母交換 但是改一改之後 10/04 14:12
11F：→ DJWS: 可以用來數逆序對 10/04 14:13
12F：推 springman: 說得也是，只是要計算交換幾次而已，謝謝。 10/04 20:10