学步园

设计一个算法，把一个含有N 个元素的数组循环右移K 位，要求时间复杂度为O（N）

考虑以下的一个数组序列1234abcd，如果右移4位，则结果应为abcd1234。

观察可知，可以通过以下的几个步骤来实现：
1、逆序排列1234：1234abcd->4321abcd  
2、逆序排列abcd： 4321abcd->4321dcba  

3、全部逆序：          4321dcba->abcd1234

#include<iostream>
using namespace std;

void Reverse(int *a,int b,int e)
{
	for(;b<e;b++,e--)
	{
		int temp=a[e];
		a[e]=a[b];
		a[b]=temp;
	}
}

void RightShift(int *a,int n,int k)
{
	k%=n;
	Reverse(a,0,n-k-1);
	Reverse(a,n-k,n-1);
	Reverse(a,0,n-1);
}

int main()
{
	int a[8]={1,2,3,4,5,6,7,8};
    RightShift(a,8,4);
	for(int i=0;i<8;i++)
		cout<<a[i];
	return 0;
}