庞果网之数组排序

我不是女神ヾ 2022-05-13 00:00 145阅读 0赞

题目详情

本题来自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。

/*********************************
    *   日期：2013-11-03
    *   作者：SJF0115
    *   题号: 题目 数组排序
    *   来源：http://hero.pongo.cn/Question/Details?ID=94&ExamID=92
    *   结果：AC
    *   来源：庞果网
    *   总结：
    **********************************/
    #include<iostream>
    #include<stdio.h>
    #include<string>
    using namespace std; 
    
    int run(const int *a,int n){
        int i,j,count=0;
        int *num = new int[n];  
        num = (int*)a;
        //每一次选一个最小的和待选序列交换
        for(i = 0;i < n;i++){
            //选择一个最小的
            int min = i;
            for(j = i+1;j < n;j++){
                if(num[min] > num[j]){
                    min = j;
                }
            }
            //最小值和待选序列第一个值交换
            if(num[min] != num[i]){
                int temp;
                temp = num[min];
                num[min] = num[i];
                num[i] = temp;
                count++;
            }
        }
        return count;
    }
    //start 提示：自动阅卷起始唯一标识，请勿删除或增加。
    int main()
    {   
        int n = 3;
        int num[4] = {3,2,1}; 
        printf("%d\n",run(num,n));
        return 0;
    } 
    //end //提示：自动阅卷结束唯一标识，请勿删除或增加。

天猫搞活动。。。。。。。。

我在用来往，用它我们就能免费语聊！11月1日到11月9日用淘宝账号登陆我还能送你2元双11现金红包！点击 [点击打开链接][Link 1],赶紧拿红包吧！

[Link 1]: http://lwurl.to/1jOgJ