### 問題描述 前面有兩節提供了不同方法解決關于將一個具有n個元素的一維向量向左旋轉i個位置。即：***[旋轉交換](http://blog.csdn.net/utimes/article/details/8762497)***和***[J](http://blog.csdn.net/utimes/article/details/8759966)****[uggling算法](http://blog.csdn.net/utimes/article/details/8759966)*。本節，提出另一種方案，塊變換解決此問題。 （來源于**《編程珠璣》第2版**的第2章第11頁問題B） 請將一個具有n個元素的一維向量向左旋轉i個位置。例如，假設n=8，i=3，那么向量abcdefgh旋轉之后得到向量defghabc。簡單編碼使用一個具有n個元素的中間向量分n步即可完成此作業。你可以僅使用幾十字節的微小內存，花費與n成比例的時間來旋轉該向量嗎？ ### 解析 直觀的想法：由于要對數組整體向左循環移動k位，那么我們就可以對數組中的每一個元素向左移動k位(超過數組長度的可以取模回到數組中)，此時總是能獲得結果的。如原串　01234567結果：34567012。觀察結果，直接的想法，我們能不能直接把待移動的串直接后面（0123456789? -- 7893456012）。此時，012是正確的位置了，但是其他元素還需調整。但是我們可以看到，把7893456變成3456789也需要向左循環移3位，這和第一步的變化是一樣的，可以用遞歸做。 **原理：**將待旋轉的向量x看成是由向量a和b組成的，那么旋轉向量x實際上就是將向量ab的兩個部分交換為向量ba **步驟**：假設a比b短(誰長，誰分成兩部分) 　　　1)將b分割為bl和br兩個部分，使得br的長度和a的長度一樣 　　　2)交換a和br，即ablbr轉換成了brbla。通過本次變換，序列a就位于它的最終位置了。 　　　3)我們需要集中精力交換b的兩個部分了，這個時候就回到了最初的問題上了,我們可以遞歸地處理b部分。 舉例：待旋轉字符串"0123456789",向左移動3位 原串：　0123456789結果：3456789012 第一步：　把**b**分成**bl**和**br**兩部分 **a???? b** **012** 3456789 ->**012**3456789(3456是一部分，789是一部分） 第二步：　把**a**與**br**交換 **br??? bl??? a** 789? 3456??012 (此時，012就是自己的最終的位置) 第三步：　之后可以遞歸處理　789 3456(**a**代表789,**b**代表3456) ---------------------------------------------------------- 全部過程 待旋轉序列：0123456789 結果：3456789012 紅色表示已排好，綠色表示分的第一部分，黑色表示分的第二部分 第一步：7893456012 第二步：4563789012 第三步：3564789012 第四步：3465789012 第五步：3456789012 ### 程序代碼 ~~~ #include <iostream> #include <assert.h> using namespace std; // 函數作用：把兩塊數據互換 // arr:待翻轉的字符串,aStart：第一塊內容的起始位置,bStart：第二塊內容的起始位置,len：交換的長度 void swap(char* arr,int aStart,int bStart,int len){ assert(arr != NULL && aStart >= 0 && bStart >= 0 && len > 0); char tmp; while(len-- > 0){ tmp = arr[aStart]; arr[aStart] = arr[bStart]; arr[bStart] = tmp; aStart++; bStart++; } //cout<<arr<<endl; } // 待旋轉字符串的起始位置start，長度len，向左移動的位數bits void Rotate(char* str,int Start,int len,int bits){ // 根據移動的位數，把待旋轉字符串分成兩部分 int leftStart = Start; int leftLen = bits; int rightStart = Start+bits; int rightLen = len-bits; // 待旋轉字符串長度為1時，直接結束 if (1 == len){ return; } // 旋轉字符串 if (leftLen > rightLen) { swap(str,leftStart,leftStart+leftLen,rightLen); Rotate(str,leftStart +rightLen,len-rightLen,len-2*rightLen); } else { swap(str,leftStart,leftStart+len-leftLen,leftLen); Rotate(str,leftStart,len-leftLen,leftLen); } } void LeftRotateString(char* str,int k){ Rotate(str,0,strlen(str),k); } int main( ){ char str[60] = "abcdefghi"; LeftRotateString(str,3); cout<<str<<endl; system("pause"); return 1; } ~~~ 基于我們分析，雖然求逆算法需要遍歷數組兩遍，塊交換和Juggling算法只需要遍歷一遍，但是Juggling算法有求素數，還是塊交換的效率高。但是從實際編碼上的難度上，還是使用求逆比較劃算。 **轉載請注明出處**：[http://blog.csdn.net/utimes/article/details/8788900](http://blog.csdn.net/utimes/article/details/8788900)