数组元素循环左移(右移)

长度为n的数组，将其元素循环左移(右移)t位

(1)最朴素的想法：每次循环左移1位，移t次

 

static void onestep(int *s,int n); /*循环左移1位*/
void rsh(int *s,int n,int t); /*循环左移t位*/

void
rsh(int *s,int n,int t){
   for(;t>0;t--)
       onestep(s,n);
}

static void
onestep(int *s,int n){
   int i,tmp;
   tmp=s[0];
   for(i=0;i<n-1;i++)
      s[i]=s[i+1];
   s[n-1]=tmp;
}


(2)改进的算法

static int gcd(int m,int n);/*m，n的最大公约数*/
void rsh(int *s,int n,int t);/*数组s循环左移t位*/

void
rsh(int *s,int n,int t){
     int i,j,k,p,tmp;
     t%=n;
     p=gcd(n,t);
     for(i=0;i<p;i++){
         k=i;j=(i+t)%n;
         tmp=s[i];
         while(j!=i){
            s[k]=s[j];
            k=j;
            j=(k+t)%n;
         }
         s[k]=tmp;
     }
}

static int
gcd(int n,int m){
     int t;
     for(t=n%m;t;){
         n=m;
         m=t;
         t=n%m;
     }
    return m;
}