旋转交换或向量旋转
最后更新于：2022-04-01 21:40:29
### 问题描述
（来源于**《编程珠玑》第2版**的第2章第11页问题B）
请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8，i=3，那么向量abcdefgh旋转之后得到向量defghabc。简单编码使用一个具有n个元素的中间向量分n步即可完成此作业。你可以仅使用几十字节的微小内存，花费与n成比例的时间来旋转该向量吗？
### 解决思路
### 方案一：
将向量x中的前i个元素复制到一个临时数组中，接着将余下的n-i个元素左移i个位置，然后再将前i个元素从临时数组中复制回x中的后面位置。该方案使用了i个额外的位置，如i足够大，过于浪费空间。
~~~
#include
void Rotate(char *a, int length, int i) {
char tmp[10];
int step = i % length;
if (step == 0) {
return;
}
int j = 0;
for (j = 0; j < step; j++){
tmp[j] = a[j];
}
tmp[step] = '\0';
for (j = step; j < length; j++){
a[j -step] = a[j];
}
while((a[length - step + j] = tmp[j]) != '\0'){
j++;
}
}
void main() {
char a[9] = "abcdefgh";
Rotate(a,8,3);
printf("%s",a);
}
~~~
### 方案二：
定义一个函数来将x向左旋转一个位置，然后调用该函数i次。该方案需要将数组移到i将，过于浪费时间。
### 方案三：
先将x[0]移临时变量t中，然后将x[i]移到x[0]中，x[2i]移到x[i]中，依次类推，直到我们又回到从x[0]中提取元素，不过在这时我们要从t中提取元素，然后结束该过程。当i=3，n=12时，该阶段将以下面的次序移到各个元素。
如果该过程不能移动所有的元素，那么我们再从x[1]开始移动，一直依次进行下去，直到移动了所有的元素时为止。
该方案过于精巧，像书中所说的一样堪称巧妙的杂技表演，非常容易出错。
### 方案四：
旋转向量x实际上就是将向量ab的两个部分交换为向量ba，这里a代表x的前i个元素。假设a比b短。将b分割成bl和br，使br的长度和a的长度一样。交换a和br，将ablbr转换成brbla。因为序列a已在它的最终位置了，所以我们可以集中精力交换b的两个部分了。由于这个新问题和原先的问题是一样的，所以我们以递归的方式进行解决。
该方案要求编码细腻，还需要深思熟虑，以确保程序具有足够的效率。
### 方案五：
[最佳]
将这个问题看作是把数组ab转换成数组ba吧，但同时也假定我们具有在数组中转置指定部分元素的函数。我们先从ab开始，转置a得到arb，再转置b得到arbr，然后再转置整个arbr得到（arbr）r，实际上就是ba。
~~~
reverse(0, i-1) /*cbadefgh*/
reverse(i, n-1) /*cbahgfed*/
reverse(0, n-1) /*defghabc*/
~~~
该转置代码在时间和空间上都很有效，并且是这么简短和简单，想出错都很难。
书中还提供了将10个元素的数组向上旋转5个位置的手摇法例子：先是掌心对着你自己，左手在右手上面，如图所示
### 代码实现
~~~
#include
void swap(int *p, int *q);
void reverse(int *vector, int index_begin, int index_end);
void revrot(int *vector, int len, int step);
int main(int argc, char **argv){
int step = 3;
int i = 0;
int vector[1024] = {1,2,3,4,5,6,7,8};
revrot(vector, 8, step);
printf("after revolve: ");
for(i = 0; i < 8; i++){
printf("%d ", vector[i]);
}
printf("\n");
}
void swap(int *p, int *q){
int temp;
temp = *p;
*p = *q;
*q = temp;
}
void reverse(int *vector, int index_begin, int index_end){
while(index_begin < index_end){
swap(vector + index_begin, vector + index_end);
index_begin++;
index_end--;
}
}
void revrot(int *vector, int len, int step){
reverse(vector, 0, step - 1);
reverse(vector, step, len - 1);
reverse(vector, 0, len - 1);
}
~~~
**转载请注明出处**：[http://blog.csdn.net/utimes/article/details/8762497](http://blog.csdn.net/utimes/article/details/8762497)
';