### 问题描述 前面有两节提供了不同方法解决关于将一个具有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)