【題目】有一個整數數組，現要求實現這個整數數組的循環右移。如：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 )。
方法四：從內存模型上出發。
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void Rotate(int* beg, int* newBeg, int* end)
{
int numElems = end - newBeg;
int* temp = (int*)malloc(sizeof(int)*(end - newBeg));
memcpy(temp, newBeg, (end - newBeg)*sizeof(int));
memmove(beg + numElems, beg, (newBeg - beg)*sizeof(int));
memcpy(beg, temp, (end - newBeg)*sizeof(int));
free(temp);
}
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for(int i = 0; i < 10; ++i)
{
Rotate(a, a + 1, a + 10);
for(int j = 0; j < 10; ++j)
printf("%d ", a[j]);
printf("\n");
}
}
方法五：先把N個字符逆序，再把前M個字符逆序，最后再把這N － M個字符逆序，即得到最
終結果。
代碼實現如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環左移
*
* 當前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發環境：Windows XP Sp2 + VC6.0
* 個人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <string.h>
#include <assert.h>
static void Swap(char *p, char *q);
static void Reverse(char *str, int i, int n);
void String_Shift_Reverse(char *str, int n)
{
int len;
assert(NULL != str);
len = strlen(str);
if (n <=0 || n >= len) {
return;
}
Reverse(str, 0, n - 1);
Reverse(str, n, len - 1);
Reverse(str, 0, len - 1);
}
static void Swap(char *p, char *q)
{
char tmp;
tmp = *p;
*p = *q;
*q = tmp;
}
static void Reverse(char *str, int i, int n)
{
int l, r;
for (l = i, r = n; l < r; l++, r--) {
Swap(&str[l], &str[r]);
}
}
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
rotate(a, a + 10 - 4, a + 10);
for(int i = 0; i < 10; ++i)
cout << a[i] << ' ';
}
方法六：這是我給出的方法，我認為是最最好的一種方法，簡直了，無語了。。。。
不過網上也有人想到了，呵呵。
但是這個方法要求被處理的數組長度或位移的位數中至少有一個奇數。
#include <stdio.h>
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i<n)
{
pos=(pos+m)%n;
int tmp=*ptr;
*ptr=*(ptr+pos);
*(ptr+pos)=tmp;
}
}
void main()
{
int a[]={1,2,3,4,5,6,7,8,9,10};
move(a,10,7);
for(int i=0;i<10;i++)
printf("%d ",a[i]);
}
該方法對位移數m沒有任何要求，只要不為負數就可以。
此外，交換兩個數據可以不用任何的臨時空間的，優化后的代碼如下：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i<n)
{
pos=(pos+m)%n;
*ptr^=*(ptr+pos);
*(ptr+pos)^=*ptr;
*ptr^=*(ptr+pos);
}
}
再優化：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i<n)
{
pos=(pos+m)%n;
*ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
}
}
再用逗號表達式優化：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(pos=(pos+m)%n,++i<n)
*ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
}
最后再優化判斷是否為偶數的運算：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!( n&1 || m&1 ))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(pos=(pos+m)%n,++i<n)
*ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
}
還有別人給出的一些方法：
分析：
最容易想到的方法有兩種：
申請一個3個字節的空間，把“ABC”復制進去，然后把剩下的字符從左到右依次移到相應的位置，最后把“ABC”再復制到最后，釋放空間，算法結束。這樣時間復雜度為O（N），空間復雜度為O（M）。
只用一個字節的輔助空間，每次把字符串循環左移一位，共移M次。這樣時間復雜度為O（M·N），空間復雜度為O（1）。
以上兩種方法雖然簡單，但時間（或空間）復雜度令人不盡滿意，有沒有時間復雜度為O（N），空間復雜度為O（1）的算法呢？下面我們來研究一下。
方案一
設字符串長度為N，臨時變量為t，算法步驟如下：
設i = 0
j = i，保存s[j]到t
把s[(j + N) % M]向前移N位到最終位置s[j % M]
j += N
如果j % M != i，則轉3；否則下一步
i++
如果i < gcd(M, N)，則轉2；否則移動完畢，算法結束
實現代碼如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環左移
*
* 當前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發環境：Windows XP Sp2 + VC6.0
* 個人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <stdio.h>
#include <string.h>
#include <assert.h>
static int gcd(int m, int n);
void StringShift(char *str, int n)
{
int i, j, len;
char tmp;
assert(NULL != str);
len = strlen(str);
if (n <= 0 || n >= len) {
return;
}
for (i = 0; i < gcd(len, n); i++) {
j = i;
tmp = str[j];
do {
str[j] = str[(j + n) % len];
j = (j + n) % len;
} while (j != i);
str[(j + len - n) % len] = tmp;
}
}
static int gcd(int m, int n)
{
int tmp;
while (n != 0) {
tmp = m % n;
m = n;
n = tmp;
}
return m;
}
在do{}while()循環中，如果k每次加n后不與len取模，可以發現k - i最后等于M、N的最小公倍數，這樣保證在循環過程中無重復下標（為什么？請自己想一下）。之所以讓for()循環做gcd(M, N)次，是因為每次do{}while()循環做M * N / （N * gcd(M, N)) = M / gcd(M, N)次，for()循環做gcd(M, N)次正好可以保證移動M次，即所有元素移動一次。（如果誰有此法的精確且清楚的數學證明，請發Email:raincatss#gmail.com）
方案二
把原字符串分成三部分ABlBr（Br與A長度相同），循環左移后為BlBrA。可以先把A與Br互換位置，變為BrBlA，然后再把Br與Bl互換，由此可以遞歸求解。
遞歸實現代碼如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環左移
*
* 當前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發環境：Windows XP Sp2 + VC6.0
* 個人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <stdio.h>
#include <assert.h>
static void Swap(char *p, char *q);
void StringShift(char *str, int len, int n)
{
int i;
assert(NULL != str);
if (len <= 0 || n <= 0 || n >= len) {
return;
}
if (n < len - n) {
for (i=0; i<n; i++) {
Swap(&str[i], &str[len - n + i]);
}
StringShift(str, len - n, n);
} else if (n > len - n) {
for (i=len-1; i>n-1; i--) {
Swap(&str[i], &str[i - n]);
}
StringShift(str + len - n, n, n + n - len);
} else {
for (i=0; i<n; i++) {
Swap(&str[i], &str[n + i]);
}
}
}
static void Swap(char *p, char *q)
{
char tmp = *p;
*p = *q;
*q = tmp;
}
為提高效率，可以把遞歸轉換為迭代，實現代碼如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環左移
*
* 當前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發環境：Windows XP Sp2 + VC6.0
* 個人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <stdio.h>
#include <assert.h>
static void Swap(char *p, char *q);
void StringShift(char *str, int len, int n)
{
int i, tmp;
char *s = str;
assert(NULL != str);
if (len <= 0 || n <= 0 || n >= len) {
return;
}
while (n != len - n) {
if (n < len - n) {
for (i=0; i<n; i++) {
Swap(&s[i], &s[len - n + i]);
}
len -=n;
} else {
for (i=len-1; i>n-1; i--) {
Swap(&s[i], &s[i - n]);
}
s += len - n;
tmp = n;
n = n + n - len;
len = tmp;
}
}
for (i=0; i<n; i++) {
Swap(&s[i], &s[n + i]);
}
}
static void Swap(char *p, char *q)
{
char tmp = *p;
*p = *q;
*q = tmp;
}