手摇算法与字符串旋转

手摇法指通过三次reverse操作，实现数组的rotation：

1

2

3

4

5

6

7

8

9

10

11

<code>/**</code>

<code>     </code><code>* 反转倒置</code>

<code>     </code><code>* 在由char[]转为sting注意不要使用tosting方法</code>

<code>     </code><code>*/</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>reverse(</code><code>char</code><code>[] chr){</code>

<code>        </code><code>int</code> <code>n=chr.length-</code><code>1</code><code>;</code>

<code>        </code><code>//使用头尾两个指针从两边向中间扫，并且不断交换两个指针的内容</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;chr.length/</code><code>2</code><code>;i++){</code>

<code>            </code><code>swap(chr,i,n--);</code>

<code>        </code><code>}</code>

<code>    </code><code>}</code>

　　

《编程珠玑》里的一个题目：

请将一个具有n个元素的一维向量x向左旋转i个位置。例如，假设n=8，i=3，

那么向量abcdefgh旋转之后得到向量defghabc。

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

<code>     </code><code>* 用于反转字符数组中index1~index2位置的这一段</code>

<code>     </code><code>* 左闭右开区间,index1&lt;=下标&lt;index2</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>reverse(</code><code>char</code><code>[] chr,</code><code>int</code> <code>index1,</code><code>int</code> <code>index2){</code>

<code>        </code><code>if</code><code>(index2-index1 &lt; </code><code>2</code><code>)</code>

<code>            </code><code>return</code><code>;</code>

<code>        </code><code>int</code> <code>j=index2-</code><code>1</code><code>;</code><code>//右侧下标</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=index1;i&lt;(index2+index1)/</code><code>2</code><code>;i++){</code>

<code>            </code><code>swap(chr,i,j--);</code>

<code>    </code> 

<code>    </code><code>/**</code>

<code>     </code><code>* 旋转</code>

<code>     </code><code>* 使用三次反转，实现旋转</code>

<code>     </code><code>* 数组注意区间取值</code>

<code>     </code><code>* @param m 从位置m处进行旋转</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>rotation(</code><code>char</code><code>[] chr,</code><code>int</code> <code>m){</code>

<code>        </code><code>//第一次倒置0~m位置</code>

<code>        </code><code>reverse(chr,</code><code>0</code><code>,m);</code>

<code>        </code><code>//第二次倒置m~最后位置</code>

<code>        </code><code>reverse(chr,m,chr.length);</code>

<code>        </code><code>//最后整体倒置</code>

<code>        </code><code>reverse(chr,</code><code>0</code><code>,chr.length);</code>

<code>    </code><code>private</code> <code>static</code> <code>void</code> <code>swap(</code><code>char</code><code>[] arr,</code><code>int</code> <code>index1,</code><code>int</code> <code>index2){</code>

<code>        </code><code>char</code> <code>temp=arr[index1];</code>

<code>        </code><code>arr[index1]=arr[index2];</code>

<code>        </code><code>arr[index2]=temp;</code>

手摇算法还可以用来优化归并排序，实现不需要额外空间开销的原地归并，即将空间复杂度降为o（1），下次再去看一下。