交换瓶子

小咪咪 2022-09-30 03:46 111阅读 0赞

交换瓶子  
有N个瓶子，编号 1 ~ N，放在架子上。  
比如有5个瓶子：  
2 1 3 5 4  
要求每次拿起2个瓶子，交换它们的位置。  
经过若干次后，使得瓶子的序号为：  
1 2 3 4 5  
对于这么简单的情况，显然，至少需要交换2次就可以复位。  
如果瓶子更多呢？你可以通过编程来解决。  
输入格式为两行：  
第一行: 一个正整数N（N<10000）, 表示瓶子的数目  
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。  
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。  
例如，输入：  
5  
3 1 2 5 4

程序应该输出：  
3

再例如，输入：  
5  
5 4 3 2 1

程序应该输出：  
2

分析:  
使用选择排序: 保证每次交换都得到一个未排数中最小(或最大)的数

#include <iostream>
    #include<iomanip>
    using namespace std;
    void swap(int *a, int *b) {
        int t = *a;
        *a = *b;
        *b = t;
    }
    int main()
    {
        int n;
        int a[10000];
        int count = 0;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> a[i]; 
        }
        //cout<< "每次交换显示:"<<endl;
        for(int j = 0; j < n; j++ ) {
            int min = j;    // j为还没排的最小数序号 
            int i;
            for(i = j; i < n; i++) {    //检查是否序号min为还没排的最小数序号 
                if(a[min] > a[i]) {     //如果不是则交换序号 最终得到最小数序号 
                    min = i;        
                }
            } 
            if(min != j) {  //交换
                swap(a[min], a[j]); 
                /*for(int look = 0; look < n; look++) { cout << setw(3) << a[look]; } cout << endl;*/
                count ++; 
            }
        }
        cout << count ;
        return 0; 
    }