問(wèn)題：有n個(gè)互異的正整數(shù)，定義將任意兩個(gè)數(shù)的位置進(jìn)行交換稱為一次操作。求將n個(gè)數(shù)變成上升序列時(shí)的最少操作數(shù)。

       當(dāng)n=11時(shí)，有序列8 3 9 1 5 6 11 4 7 10 2，現(xiàn)在要把它通過(guò)交換變成上升序列1 2 3 4 5 6 7 8 9 10 11。可以看出，'8'應(yīng)該放在第8個(gè)位置，而在第8個(gè)位置的'4'應(yīng)該被交換到第4個(gè)位置，而在第4個(gè)位置的‘1’應(yīng)該被交換到第1個(gè)位置，而此時(shí)在第1個(gè)位置的正是一開始就拿來(lái)交換的數(shù)字'8'，也就是說(shuō)，數(shù)字'8' '4' '1'形成了一個(gè)循環(huán)圈，交換2次(8-4,4-1)，則數(shù)字‘1’‘4’‘8’都能到達(dá)最終位置了，在之后的交換中不會(huì)在用到這3個(gè)數(shù)字。同理，對(duì)序列的其他數(shù)字也如此處理，可以得出其余4個(gè)循環(huán)圈，(3 9 7 11 2)，(5)，(6)，(10)。那么，最少交換次數(shù) = (3-1)+(5-1) +(1-1) +(1-1)+(1-1) = 6

       假設(shè)n個(gè)數(shù)分成k個(gè)“循環(huán)圈”，每個(gè)“循環(huán)圈”的個(gè)數(shù)分別是a1，a2，……，ak，那么最少交換次數(shù) = (a1-1)+(a2-1)+……+(ak-1) = (a1+a2+……+ak) - 1 * k = n - k

因此，最少交換次數(shù) = 序列個(gè)數(shù) - “循環(huán)圈”個(gè)數(shù)

本文參考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的是誰(shuí)	int rank[maxn]; //rank[i]表示第i個(gè)排第幾	memset(sa, 0, sizeof(sa));	memset(rank, 0, sizeof(rank));	jishu_sort(a, n, sa, rank); //用計(jì)數(shù)排序?qū)數(shù)組進(jìn)行升序排序	int sign[maxn]; //sign[i]表示第i個(gè)數(shù)屬于第幾個(gè)“循環(huán)圈”	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])	//找出這個(gè)循環(huán)圈的其他數(shù)字，并寫上編號(hào)			{				sign[x] = circle; //寫號(hào)				x = sa[rank[x]];  //找下一個(gè)			}		}	//output answer	PRintf("%d/n", n - circle);}int main(){	init();	solve();	return 0;}