作者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/cn.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