Question

一道ACM编程题 求算法思路.

给出一些无序的数
比如5 3 4 2 1
每次可以交换其中任意2个数

现在求最少的交换次数 使序列变得从小到大有序

怎么求最小的交换次数呢？
说下思路就行了
希望算法够快

Answer 1

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

Answer 2

应该是求排列的逆序数，一个排列中某个元素的逆序数是在这个元素之前比这个元素大的元素的个数，而排列的逆序数则是每个元素逆序数的和。至于求逆序数的好算法，我不清楚。

Answer 3

不是逆序数，差点搞混了，应该这样解：比如有数组A,升序排序后得数组B
for(int i=0;i<n;i++){
if(A[i]!=B[i]){
在A数组中，从后往前找，直到找到一个比A[i]小的数，交换之，并记录交换次数
}
}
最后交换的总次数应该就是楼主要的答案

Answer 4

0

Answer 5

排序