数组的循环移位

    有数组a[],有n个元素，实现它的循环移位，向左移位k位。有多种方法，这里仅列举三种：

（1）申请O(k)的附加空间，先将要移位的k位放入附加空间，把后面的元素前移，然后将这k位数加到数组的尾部。这种方法消耗的空间较多。

（2）只使用O（1）的空间，定义函数，函数实现的功能是每次移动一位，k次调用函数，即可实现循环移位，这种方式需要多次调用函数，程序的效率会降低

（3）使用翻转的方法，假设要左移的k位即为a,后面n-k位记为b,将a,b分别翻转得到a’,b’,在对a’b’翻转，即(a’b’)=ba,这样也可以实现循环移位。这个算法的时间复杂度为O(n),空间复杂度为O(1).

下面的代码中shift()函数对应（1）的方法，shift2()对应（2）的方法，shift3()对应（3）的方法

# include <iostream>
using namespace std;
# include <stdlib.h>
int main()
{
	void shift(int a[],int n,int s);
	void shift2(int a[],int n,int m);
	void shift3(int a[],int n,int m);
	int a[10]={1,2,3,4,5,6,7,8,9,0};
	int i=0;
	//shift(a,10,4);
	//shift2(a,10,4);
	shift3(a,10,4);
	for(i=0;i<10;i++)
		cout<<a[i]<<endl;
system("pause");
return 0;
}
void shift(int a[],int n,int s)   //上文中的（1）方法
{
	int *b=(int *)malloc(s*sizeof(int));
	int i=0;
if(s>=n)
{
cout<<"error"<<endl;
exit(-1);
}
for(i=0;i<s;i++)
	b[i]=a[i];
for(i=s;i<n;i++)
	a[i-s]=a[i];
for(i=0;i<s;i++)
	a[n-s+i]=b[i];
}

void shiftone(int a[],int n)   //左移一位，用于方法（2）
 {
	int t;
	int i=0;
	t=a[0];
	for(i=1;i<n;i++)
		a[i-1]=a[i];
	a[n-1]=t;
}

void shift2(int a[],int n,int m)   //上文中（2）的方法
{
int i=0;
for(i=0;i<m;i++)
	shiftone(a,n);
}

void shift3(int a[],int n,int m)  //（3）的方法，翻转移位
{
	int i,j,t;
	for(i=0;i<=(m-1)/2;i++)     //前m位翻转
 	{
	t=a[i];
	a[i]=a[m-i-1];
	a[m-i-1]=t;
	}
	for(i=m;i<=(n+m-1)/2;i++)   //后面n-m位翻转
	{
	t=a[i];
	a[i]=a[n-1-(i-m)];
	a[n-1-(i-m)]=t;
	}
	for(i=0;i<=(n-1)/2;i++)     //翻转整个数组
	{
	t=a[i];
	a[i]=a[n-1-i];
	a[n-1-i]=t;
	}
}

数组的循环移位,布布扣,bubuko.com

数组的循环移位

原文：http://blog.csdn.net/u011608357/article/details/21788567