求一个c++的代码~题目：给定一个数列，给它从小到大排列，每次交换两个数，求最少的交换次数~思路：找出形成单循环的个数。（单循环：一些数原来不在排序后自己的位置，却占据排序

Question

求一个c++的代码~
题目：给定一个数列，给它从小到大排列，每次交换两个数，求最少的交换次数~
思路：找出形成单循环的个数。（单循环：一些数原来不在排序后自己的位置，却占据排序后那些数共占据 的位置，如3412排序后是1234，其中2 4原来不在排序后自己的位置，但却占了排序后的2 4应该占得 位置。（语文不好解释不大清楚-.-））。然后把原本数列不对应的数的个数减去单循环的个数就是 最 少交换次数。
不知道我思路对不对= =不对的话求大神帮忙解释一下。顺便上一下代码，怎么找出单循环的个数-.-。

Answer 1

首先告诉你 你说的3412只是一种特殊情况
排序分为 插入 交换 选择 归并 基数排序 基数排序可以不用交换 例如桶排序 题目要求交换 那就用冒泡排序
冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，最后的元素应该会是最大的数。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
例如你要排列5个数 34 23 45 56 89
step1 23 34 45 56 89
这是特殊情况 一次排完
再来 个复杂的 46 35 88 21 9 13
s1 35 46 21 9 13 [88]
s2 35 21 9 13 [46 88]
s3 21 9 13 [35 46 88]
s4 9 13[ 21 35 46 88 ]
比如写一个排序5个数的代码
#include void main()
{
int i, j, temp;
int a[5];
for (i = 0; i < 5; i++)
{
scanf("%d,", &a[i]);
}
for (j = 0; j < 4; j++)
{
for (i = 0; i < 4 - j; i++)
{
if (a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
} for (i = 0; i < 5; i++)
{
printf("%d,", a[i]);
}
printf("");
}
关于时间复杂度的问题你可以百度一下 你也可以查一下桶排序