(排序算法的应用7.3.8)UVA 299 Train Swapping(使用冒泡排序回计算逆序对数)

(排序算法的应用7.3.8)UVA 299 Train Swapping(使用冒泡排序来计算逆序对数)

/*
 * UVA_299.cpp
 *
 *  Created on: 2013年11月3日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 55;

int main() {
	int a[maxn];

	int t;
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		int i;
		for (i = 0; i < n; ++i) {
			scanf("%d", &a[i]);
		}

		int j;
		int ans = 0;
		for(i = 0 ; i < n ; ++i){//冒泡排序
			for(j = i+1; j < n ; ++j){
				if(a[i] > a[j]){
					int temp = a[i];
					a[i] = a[j];
					a[j] = temp;

					ans++;//逆序对数+1
				}
			}
		}

		printf("Optimal train swapping takes %d swaps.\n", ans);

	}

	return 0;
}