一道ACM编程题求算法思路.给出一些无序的数比如5 3 4 2 1每次可以交换其中任意2个数现在求最少的交换次数使序列变得从小_其他解答

一道ACM编程题求算法思路.
给出一些无序的数
比如5 3 4 2 1
每次可以交换其中任意2个数
现在求最少的交换次数使序列变得从小到大有序
怎么求最小的交换次数呢?
说下思路就行了
希望算法够快

人气：276 ℃　时间：2020-07-25 22:29:48

解答

你需要找环.
每一个长度为n的环要排好, 需要n-1次操作.
如5 3 4 2 1
有两个环,
5 1
3 4 2
所以需要1+2=3次操作
分别是
1和5换
3和2换
3和4换