首先定义运算"swap"：从数组中移除一个元素，然后放在该数组的尾部。 用最少的“swaps"将数组排序。 比如，[3 1 2 4]，最少需要[3 1 2 4]->[1 2 4 3]->[1 2 3 4]

gistfile1.cpp

#include <stdio.h>

/*
首先定义运算"swap"：从数组中移除一个元素，然后放在该数组的尾部。
用最少的“swaps"将数组排序。
比如，[3 1 2 4]，最少需要[3 1 2 4]->[1 2 4 3]->[1 2 3 4]

程序的输入为小于65536的正整数，数组长度小于100
*/

#define MAX_LEN 100
#define MAX_VAL 65536
#define MIN_VAL -1

/*
实现"swap"操作
*/
void moveToTail(int a[], int idx, int size){
    int tmp = a[idx];
	while(idx<size-1){
		a[idx] = a[idx+1];
		idx++;
	}
	a[idx] = tmp;
}

/*
返回最小逆序数的坐标（数组正序则返回最后一个数的坐标）
*/
int detectReverse(int a[], int size){
	int i=size-1, minVal=a[size-1], minRevVal=MAX_VAL, minRevIdx=size-1;
	while(--i>=0){
		if(a[i]>minVal){
			// 逆序数
			if(a[i]<minRevVal){
				//更新最小的逆序数值
				minRevVal = a[i];
				minRevIdx = i;
			}
		}else if(a[i]<minVal){
			// 更新最小值
			minVal = a[i];
		}
	}
	return minRevIdx;
}
int main(){
	int a[MAX_LEN];
	int i, revIdx, count, size;
	while(printf("input array size:") && scanf("%d", &size) && size>0){
		printf("input %d positive number:", size);
		for(i=0; i<size; i++){
			scanf("%d", &a[i]);
		}
		count = 0;
		while((revIdx = detectReverse(a, size)) < size-1){
			moveToTail(a, revIdx, size);
			count ++;
		}
		printf("min swap count:%d\n", count);
	}
}