給一字串全由字母 A-Z 組成
將其依字母順序由小到大排序
限定只能相鄰字母兩兩交換
問至少要交換幾次
能排序完成
Ex.
Input : DCBA
Output: 6
請問這有好的算法嗎
謝謝 :)

從merge sort下手

所求為逆序對的數目, 不過基本上就是 merge sort...

謝謝 c 大 和 L 大L 大好厲害，可以想到是求「逆序對」數目，讚歎！

merge sort 可以做到「只能相鄰字母交換」嗎？感覺上好像 bubble sort 與 inersetion sort 可以。抱歉，打錯字，insertion sort。

用什麼sort都可以,只是merge sort能O(nlgn)算逆序數

那為什麼不用counting sort? 聽起來更快springman: merge sort不能做到相鄰字母交換 但是改一改之後可以用來數逆序對

說得也是，只是要計算交換幾次而已，謝謝。