庞果网之数组排序

题目详情

本题来自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 //提示：自动阅卷结束唯一标识，请勿删除或增加。