2860 - 【设计型】第11章：指针和数组 最少的交换
时间限制 : 1 秒
内存限制 : 128 MB
现在给你一个由n个互不相同的整数组成的序列，现在要求你任意交换相邻的两个数字，使序列成为升序序列，请问最少的交换次数是多少？
题目输入
输入包含多组测试数据。每组输入第一行是一个正整数n（n<500000），表示序列的长度，当n=0时，结束输入。当n！=0时，接下来的n行，每行一个整数a[i]（0<=a[i]<=999999999），表示序列中第i个元素。整体的测试数据组数不超过8组。
题目输出
对于每组输入，输出使得所给序列升序的最少交换次数，并输出回车。
输入/输出样例
输入格式
5 9 1 0 5 4 3 1 2 3 0
输出格式
6 0
C语言解答
#include<stdio.h> #include<stdlib.h> #define N 10 int main() { int n; int count[N] = {0}; int count_n = 0; int i, j; int temp; int b; do { scanf("%d", &n); if(n == 0) break; int *a = (int *)malloc(n*sizeof(int)); for(i = 0; i < n; i++) { scanf("%d", &a[i]); } do { for(i = 0; i < n-1; i++) { if(a[i] > a[i+1]) { count[count_n]++; temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } } for(i = 0; i < n-1; i++) { if(a[i] < a[i+1]) { b = 1; continue; } else { b = 0; break; } } }while(!b); count_n++; }while(n); for(i = 0; i < count_n; i++) { printf("%d\n", count[i]); } return 0; }