楼主:
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不能做到相邻字母交换 但是改一改之后可以用来数逆序对