数组排序

数组排序

　　本题来自caopengcs，只要你有兴趣，每个人都可以出题（出题入口在主页右侧边栏“贡献题目”内），以下是题目详情：给定一个包含1-n的数列，我们通过交换任意两个元素给数列重新排序。求最少需要多少次交换，能把数组排成按1-n递增的顺序，其中，数组长度不超过100。

例如：原数组是3,2,1，我们只需要交换1和3就行了，交换次数为1，所以输出1。原数组是2,3,1，我们需要交换2和1，变成1,3,2，再交换3和2，变为1，2，3，总共需要的交换次数为2，所以输出2。

函数头部： C/C++ int run(const int *a,int n); java class solution { public static int run(int [] a) }

我采用的是最原始，最笨重的方法，复杂度应该是O(N^2)；函数run(const int *a,int n)中的const int *a是存放在静态数据区，所以不可以修改，我定义了一个*arr，将a 指向的内存区域的数值赋值给 arr 所申请的内存空间，长度为100，时间忽略不计；然后按照1 - n遍历 arr[n]，若arr[n] == n + 1，则continue；否则，在后面的数列中找到满足条件arr[n] == n + 1的整数 arr[k]，将arr[n] 与arr[k]做交换，同时arr[k]cnt++（cnt表示交换次数）；循环结束表示已经排号序列返回整数cnt.

　　群里面说了，之前做过的题目可能会重新开放，所以不要在解题报告里面贴出完整代码，我觉得，贴出代码的目的是让大家检查自己的程序漏洞及错误所在，而不是直接复制粘贴然后通关的，显然这就违背了庞果网及其相关人员的初衷，仅此。

for(iterX = 0; iterX < n - 1; iterX++)
    {
        if(arr[iterX] == iterX + 1)
        {
            continue;
        }
        for(iterY = iterX + 1; iterY < n; iterY++)
        {
            if(arr[iterY] == iterX + 1)
            {
                temp = arr[iterX];
                arr[iterX] = arr[iterY];
                arr[iterY] = temp;
                cnt++;
            }
        }
    }

View Code

　　这道题目，我想解法应该是非常多的，充分发挥自己的想象力，好好思考一下这道题目吧。

测试用例：

用例1：a[3] = {3 ,2 ,1} n = 3; cnt = 1

用例2：a[4] = {2，1， 4， 3} n = 4; cnt = 2

用例3：a[4] = {2，3， 4， 1} n = 4; cnt = 3

用例4：a[4] = {2，4， 1， 3} n = 4; cnt = 3