换位.c

经典算法之换位和工作安排

//a[0:k]与a[k+1:n-1]换位
//时间复杂度O(n),辅助存储空间O(1)

#include "stdio.h"
// #define n 7

void Change(int a[],int LO,int MI,int HI){//换位
	int i,temp;
	if((HI==MI+1)&&(MI==LO)){  //若数组只有两个元素
		temp=a[LO];
		a[LO]=a[MI+1];
		a[MI+1]=temp;
		return;
	//	goto END;
	}
	if((HI-MI-1)>(MI-LO)){    //若n-1-k>k
		for(i=0;i<=MI-LO;i++){
			temp=a[LO+i];
			a[LO+i]=a[MI+1+i];
			a[MI+1+i]=temp;
		}
		Change(a,MI+1,2*MI+1-LO,HI);  //从2k+1处到n-1的数向前交换
	}
	if((HI-MI-1)<(MI-LO)){   //若n-1-k<k
		for(i=0;i<=HI-MI-1;i++){
			temp=a[HI-i];
			a[HI-i]=a[MI-i];
			a[MI-i]=temp;
		}
		Change(a,LO,2*MI-HI,MI);   //从0到2k-n+1的数向前交换
	}
//END:;
}

void main(){
//	int a[n]={3,5,6,8,4,1,7};
	int i,k=-1,n;
    int a[100];
	printf("INPUT the number of element of array: ");  //输入元素个数
	scanf("%d",&n);
    printf("input the value of element of array: "); //输入数组元素的值
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
    printf("\n");
	printf("Input the value of k(0<=k<=%d).\n",n);   //输入k的值
	while(k<0||k>n)
		scanf("%d",&k);
	printf("Before:");    //原来的数组  
	for(i=0;i<n;i++)
		printf("%d  ",a[i]);
	printf("\nk=%d\n",k);
	Change(a,0,k,n-1);  //将a[0:k]与a[k+1,n-1]换位
	printf("After:");     //换位后的数组
	for(i=0;i<n;i++)
		printf("%d  ",a[i]);
	printf("\n");
}