内存移动算法
原文参见《程序员》杂志2006年第6期。现对原文做部分摘录，并给出自己的算法。
问题： 对于有K个元素的数组int a[k]={.......};写一个高效算法将数组内容循环左移m位，
比如：int a[6]={1,2,3,4,5,6}，循环左移3位后得到结果{4,5,6,1,2,3}.
要求：1.不允许另外申请数组空间，但可以申请少许变量；
2.不允许采用每次左移。
最直观的想法，就是从第一个元素开始，把他一步移动到最终目的位置，而该位置原有的元素的值取出，移动到它的新位置。递归进行这个步骤。
首先，我们在数学上很容易理解，这是一个一一对应映射，绝不会在一个位置上出现两次移动。所以不会出现移动的递归过程中途指向了已经移动过的元素。
那么，这个递归过程唯一的终止条件就是，当前移动的元素，目的位置就是移动过程的起始位置。
如果按照元素的索引下标标示元素，0到k-1中的任意元素i，会移动到什么位置？
对于任意的i，它的新位置i'＝((k-m) + i)%k.
那么，我们可以定义这个循环链，取整数i0,使得0＝<i0<m,定义i1=((k-m) + i0)%k,i2=((k-m) + i1)%k....ix=((k-m) + ix-1)%k.当ix=i0时循环终止。此时有i0=ix=((k-m) + ix-1)%k=....
=(x(k-m) + i0)%k
因为我们知道0<i0<m,所以有0=x(k-m)%k,也就是说，x(k-m)=yk,因为我们是遇到第一个x(k-m)=yk就终止，显然等号左右的值就是k-m和k的最小公倍数。根据数论知识，我们知道，k,m,k-m这三个数有最大公约数q，使得k=aq,m=bq,k-m=cq,a,b,c三个数两两互质，进而推出x=a,y=c。也就是说，这个递归过程会经历a步。
因为我们知道整个过程一共a步，k=aq，那么i到ix的序列会形成一个步长为q的等差序列，所以我们要移动整个0到k-1的区间，应该对0到q-1的元素应用这个递归算法。
该算法的时间复杂度为O(n)，空间复杂度为O(1).
int CommonFactor(int dividend,int divisor)//求最大公约数函数
{
if(dividend<divisor)
{
int temp=dividend;
dividend=divisor;
divisor=temp;
}
int remainder=dividend%divisor;
while(remainder!=0)
{
dividend=divisor;
divisor=remainder;
remainder=dividend%divisor;
}
return divisor;
}
void shift1(int a[],int k,int m)//k是数组a的元素个数，m是循环左移m位
{
int i,j,n,q=CommonFactor(k,k-m);
for(n=0;n<q;n++)
{
int temp=x[n]; i=n;j=(i+m)%k;
while(j!=n)
{
x[i]=x[j];
i=j;
j=(i+m)%k;
}
x[i]=temp;
}
}
同理可以分析循环右移m位的算法
void shift1(int a[],int k,int m)//k是数组a的元素个数，m是循环右移m位
{
int i,j,n,q=CommonFactor(k,m);
for(n=0;n<q;n++)
{
int temp=x[n]; i=n;j=(k+i-m)%k;
while(j!=n)
{
x[i]=x[j];
i=j;
j=(k+i-m)%k;
}
x[i]=temp;
}
}
