数组循环右(左)移

把一个含有n个元素的数组循环右移/左移k位。

下面是具体的算法

一、时间复杂度为O(N*N)的算法

void rightshift_1(int a[],int n,int k) //n为数组长度，k为数组右移的位数

{
    int i;
    int t;
    
    k = k % n;    

    while (k--)
    {
        t = a[n - 1];
        
        for (i = n - 1;i > 0;i--)
        {
            a[i] = a[i - 1];
        }
        
        a[0] = t;
    }
}

二、时间复杂度为O(N)的算法

void reverse(int a[],int left,int right) //将数组内a[left]到a[roght]的元素逆置

{
    int t;
    
    for (;left < right;left++,right--)
    {
        t = a[left];
        a[left] = a[right];
        a[right] = t;
    }
}

void rightshift_2(int a[],int n,int k)//实现循环右移

{
    k = k % n;
    reverse(a,0,n - k - 1);
    reverse(a,n - k,n - 1);
    reverse(a,0,n - 1);
}

例如：

abcde123循环右移3为

步骤1：将a[0]~a[4]逆置，得到edcba123

步骤2：将a[5]~a[7]逆置，得到edcba321

步骤3：将a[0]~a[7]逆置，得到123abcde

循环左移的算法和循环右移基本相同