旋转交换(编程珠玑)

问题
解决思路
- 方法1
- 方法2
程序代码
- 方法2的代码

问题

请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3，那么向量abcdefgh旋转之后得到向量defghabc。简单编码使用一个具有n个元素的中间向量分n步即可完成此作业。你可以仅使用几十字节的微小内存，花费与n成比例的时间来旋转该向量吗？

解决思路

方法1

将向量x中的前i个元素复制到一个临时数组中，接着将余下的n-i个元素左移i个位置，然后再将前i个元素从临时数组中复制回x中的后面位置。
该方案使用i个额外的位置，如i足够大，过于浪费空间。

方法2

将这个问题看作是把数组ab转换成数组ba吧，但同时也假定我们具有在数组中转置指定部分元素的函数。我们先从ab开始，转置a得到$a^rb$，再转置b得到$a^rb^r$，然后再转置整个$a^rb^r$得到$(a^rb^r)^r$，实际上就是ba。

reverse(0, i-1)
reverse(i, n-1)
reverse(0, n-1)

该转置代码在时间和空间上都很有效，并且是这么简短和简单，想出错都很难。

程序代码

方法2的代码

#include <stdio.h>

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;
}

//@vector：数组
//@index_begin：开始位置
//@index_end：结束位置
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--;
   }
}

//@vector：数组
//@len：数组长度
//@step：反转位置
void revrot(int *vector, int len, int step)
{
   reverse(vector, 0, step - 1);
   reverse(vector, step, len - 1);
   reverse(vector, 0, len - 1);
}