当前位置：编程学习 > C/C++ >>

(应用排序算法编程7.2.1)UVA 10327 Flip Sort(使用冒泡排序来求逆序对)

 
/* 
 * UVA_10327.cpp 
 * 
 *  Created on: 2013年11月1日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
#include <cstdio>  
  
using namespace std;  
  
const int maxn = 1010;  
int main(){  
    int a[maxn];  
  
    int n;  
    while(scanf("%d",&n)!=EOF){  
        int i;  
        for(i = 1 ; i <= n ; ++i){  
            scanf("%d",&a[i]);  
        }  
  
        bool flag = true;  
        int ans = 0;  
        while(flag){//只要序列中出现逆序对,就不断的从前往后扫  
            flag = false;  
            for(i = 1 ; i < n ; ++i){  
                if(a[i] > a[i+1]){  
                    int temp = a[i+1];//这三行也可以换成swap(a[i],a[i+1])  
                    a[i+1] = a[i];  
                    a[i] = temp;  
  
                    ans++;  
                    flag = true;  
                }  
            }  
        }  
  
        printf("Minimum exchange operations : %d\n",ans);  
    }  
  
    return 0;  
}