作者:
cutekid (可愛小孩子)
2014-10-03 08:54:24給一字串全由字母 A-Z 組成
將其依字母順序由小到大排序
限定只能相鄰字母兩兩交換
問至少要交換幾次
能排序完成
Ex.
Input : DCBA
Output: 6
請問這有好的算法嗎
謝謝 :)
作者:
ckc1ark (偽物)
2014-10-03 09:06:00從merge sort下手
作者:
LPH66 (-6.2598534e+18f)
2014-10-03 09:19:00所求為逆序對的數目, 不過基本上就是 merge sort...
作者:
cutekid (可愛小孩子)
2014-10-03 09:36:00謝謝 c 大 和 L 大L 大好厲害，可以想到是求「逆序對」數目，讚歎！
merge sort 可以做到「只能相鄰字母交換」嗎？感覺上好像 bubble sort 與 inersetion sort 可以。抱歉，打錯字，insertion sort。
用什麼sort都可以,只是merge sort能O(nlgn)算逆序數
作者:
DJWS (...)
2014-10-04 14:07:00那為什麼不用counting sort? 聽起來更快springman: merge sort不能做到相鄰字母交換 但是改一改之後可以用來數逆序對