## 【我解C語言面試題系列】004 數組的循環右移問題
**數組的循環右移**
【題目】有一個整數數組，現要求實現這個整數數組的循環右移。如：1，2，3，4，5 則循環右移兩位后結果是：4，5，1，2，3。
**方法一：**（最最容易想到的辦法）
~~~
void RightCircleShift_00(int buffer[],int shift)
{
?? int i,j,tt;
??
?? for(i=0;i<shift;i++)
?? {
????? tt = buffer[ARRSIZE-1];
????? for(j=ARRSIZE-1;j>0;j--)
????????? buffer[j] = buffer[j-1];?
????? buffer[0] = tt;
?? }
}
~~~
這個辦法是用兩個循環來控制，內循環每次向右移動一位，外循環則用來限制移動的位數。算法需要執行 ARRSIZE * ShiftValue次，時間復雜度是O( N2 )。
**方法二：**（由方法一得到的遞歸程序）
~~~
void RightCircleShift_01(int buffer[],int shift)
{
?? int *p,tt;
??
?? tt = *(buffer+ARRSIZE-1);
?? for(p = buffer+ARRSIZE-1;p > buffer;p--)
????? *p = *(p-1);
??
?? *buffer = tt;
?? shift--;
?? if(shift > 0)
?????? RightCircleShift_00(buffer,shift);
}
~~~
這個程序跟方法一類似，區別就是它是用遞歸來實現的。同樣需要執行ARRSIZE * ShiftValue次，時間復雜度也是O( N2 )。
**方法三**：?
~~~
void RightCircleShift_02(int buffer[],int shift)
{
?? int *title,*r,*p;
??
?? if(shift == 0)
????? return;
??
?? shift = shift % ARRSIZE;
??
?? title = (int *)malloc(sizeof(int)*shift);
?? if( title == NULL )
????? return;
??
?? r = buffer + (ARRSIZE - shift);
?? memcpy(title, r, shift * sizeof(int));
?? p = buffer + shift;
?? memmove(p, buffer, (ARRSIZE - shift) * sizeof(int));
?? memcpy(buffer, title, shift * sizeof(int));
??
?? free(title);
}
~~~
這個算法需要移動位數大小的臨時輔助空間。如需移動兩位，則申請兩個的空間，然后把從右邊起的兩個元素拷貝的臨時輔助空間，然后前面的元素向后移動兩位，最后再把臨時空間里面的兩個元素拷貝到前面的兩位即可完成循環右移。需要執行 ARRSIZE次，時間復雜度是O( N )。
**方法四：
~~~
void RightCircleShift_03(int buffer[],int shift)
{??
?? if(shift <= 0)
????? return;
?? if( (shift & 1) == 0)
?? {
????? BufferShiftEvenNumber(buffer,shift-1);
????? BufferShiftEvenNumber(buffer,1);
?? }
?? else
????? BufferShiftEvenNumber(buffer,shift);
?? ???
}
void BufferRightShiftEvenNumber(int buffer[],int shift)
{
?? int i,j,tt,res;
?? res = buffer[0];
?? for (i=0,j=0; i<ARRSIZE; i++)
?? {
????? tt = res;
????? res = buffer[(j+shift)%ARRSIZE];
????? buffer[(j+shift)%ARRSIZE] = tt;
????? j = (j+shift) % ARRSIZE;
?? }
}
~~~
這個算法并不需要開額外的輔助空間，而且時間復雜度同樣也是O( N )。BufferRightShiftEvenNumber函數是這個算法的核心，該函數只能實現每次向右移動奇數位元素。如果要移動的位數是偶數的時候就需要把該數分解為兩個奇數，n = (n – 1) + 1 。
**方法五：**
~~~
void RightCircleShift_04(int buffer[],int shift)
{
?? shift %= ARRSIZE;
?? ReverseArray(buffer,1,ARRSIZE);
?? ReverseArray(buffer,1,shift);
?? ReverseArray(buffer,shift+1,ARRSIZE);
}
void ReverseArray(int buffer[],int start,int end)
{
?? int i,tt;
?? if(end > ARRSIZE)
????? return;
?? start -= 1;
?? end -= 1;
?? while(start < end)
?? {
????? tt = buffer[start];
????? buffer[start++] = buffer[end];
????? buffer[end--] = tt;
?? }
}
~~~
這個辦法也是很不錯，需要兩次掃描數組即可，時間復雜度O(N)。這個辦法跟方法四移動偶數個元素的情況一樣，都是需要兩次掃描數組。當然如果是移動奇數個元素的話，則不如方法四有效，方法四只需要掃描一次數組就可以了。
算法是網友[luodongshui](http://blog.csdn.net/luodongshui/)提出的：
1、先將整個數組反轉。
2、然后再反轉前shift個元素。
3、接著再反轉后N-shift個元素。
