求将n个数变成上升序列时的最少交换次数

问题：有n个互异的正整数，定义将任意两个数的位置进行交换称为一次操作。求将n个数变成上升序列时的最少操作数。

       当n=11时，有序列8 3 9 1 5 6 11 4 7 10 2，现在要把它通过交换变成上升序列1 2 3 4 5 6 7 8 9 10 11。可以看出，'8'应该放在第8个位置，而在第8个位置的'4'应该被交换到第4个位置，而在第4个位置的‘1’应该被交换到第1个位置，而此时在第1个位置的正是一开始就拿来交换的数字'8'，也就是说，数字'8' '4' '1'形成了一个循环圈，交换2次(8-4,4-1)，则数字‘1’‘4’‘8’都能到达最终位置了，在之后的交换中不会在用到这3个数字。同理，对序列的其他数字也如此处理，可以得出其余4个循环圈，(3 9 7 11 2)，(5)，(6)，(10)。那么，最少交换次数 = (3-1)+(5-1) +(1-1) +(1-1)+(1-1) = 6

       假设n个数分成k个“循环圈”，每个“循环圈”的个数分别是a1，a2，……，ak，那么最少交换次数 = (a1-1)+(a2-1)+……+(ak-1) = (a1+a2+……+ak) - 1 * k = n - k

因此，最少交换次数 = 序列个数 - “循环圈”个数

本文参考http://blog.csdn.net/wangxugangzy05/article/details/42454111

参考程序：

#include<stdio.h>#include<string.h>#define maxn 10001int a[maxn];int n;void init(){	scanf("%d", &n);	for(int i = 1; i <= n; i++)		scanf("%d", &a[i]);}void jishu_sort(int a[], int n, int sa[], int rank[]){	int count[maxn];	memset(count, 0, sizeof(count));	int i;	for(i = 1; i <= n; i++)		count[a[i]]++;	for(i = 1; i < maxn; i++)		count[i] += count[i-1];	for(i = 1; i <= n; i++)	{		rank[i] = count[a[i]]--;	}	for(i = 1; i <= n; i++)		sa[rank[i]] = a[i];}void solve(){	int sa[maxn]; //sa[i]表示排第i的是谁	int rank[maxn]; //rank[i]表示第i个排第几	memset(sa, 0, sizeof(sa));	memset(rank, 0, sizeof(rank));	jishu_sort(a, n, sa, rank); //用计数排序对a数组进行升序排序	int sign[maxn]; //sign[i]表示第i个数属于第几个“循环圈”	memset(sign, 0, sizeof(sign));		int circle = 0;	for(int i = 1; i <= n; i++)		if(!sign[i])		{			sign[i] = ++circle;			int x = sa[rank[i]];			while(!sign[x])	//找出这个循环圈的其他数字，并写上编号			{				sign[x] = circle; //写号				x = sa[rank[x]];  //找下一个			}		}	//output answer	PRintf("%d/n", n - circle);}int main(){	init();	solve();	return 0;}