Rotate Array

from here

1. 问题描述

将一个具有n个元素的向量，向左旋转i个位置。

例如，具有8个元素的向量abcdefgh，向左旋转3个元素的结果是defghabc。

第二种解法，这种解法来自于C++ STL的rotate调用的源码，代码如下：

template <class ForwardIterator>  
  void rotate ( ForwardIterator first, ForwardIterator  middle,     
                 ForwardIterator last )     
{   
  ForwardIterator next = middle;    
  while (first!=next)      
  {     
     swap (*first++,*next++);   
     if (next==last) next=middle; //注意，这两个if不能交换位置  
      else if (first == middle) middle=next;      
  }  
}  

上面的伪代码可能不太好理解，我们来分析一下。

假设数组有N个元素，旋转i位，且(N>i)，我们首先考虑i < N-i的情况，我们可以把数组分成三部分，分别是 ab1 b2，其中，a的长度等于b1的长度,然后算法执行一轮以后，就得到 b1ab2，剩下要做的事情就是交换ab2的顺序，且中点应该在ab2交接的地方，所以有middle=next，假设此时b2的长度小于a，则将划分为a1a2b2，然后再执行一次while循环，整个数组就变成了b1b2a2a1,现在是要交换a2和a1的顺序即可。

交换a2和a1的顺序其实和交换a和b的顺序是一样的，只是元素更少了。

完整的代码如下所示：

#include <stdio.h>
#include <string.h>

void swap(char *p, char *q)
{
    if ( p == NULL || q == NULL) return;

    char temp = *p;
    *p = *q;
    *q = temp;
}


void rotate(char* first, char* middle, char* last)
{
    char *next = middle;
    while( first != next)
    {
        swap( first++, next++);
        if (next == last){ next = middle;}
        else if ( first == middle ) { middle = next;}
    }
    return;
}


int main(int argc, char* argv[])
{

   char str[] = "abcdefgh";
   int n = strlen(str);
   int i = 3;
   rotate( str, str + i, str + n);
   printf("%s\n", str);
   return 0;
}