手摇法指通过三次reverse操作，实现数组的rotation：
1.如何实现字符串倒置
|
1
2
3
4
5
6
7
8
9
10
11
|
/**
* 反转倒置
* 在由char[]转为Sting注意不要使用toSting方法
*/
public
static
void
reverse(
char
[] chr){
int
n=chr.length-
1
;
//使用头尾两个指针从两边向中间扫，并且不断交换两个指针的内容
for
(
int
i=
0
;i<chr.length/
2
;i++){
swap(chr,i,n--);
}
}
|
2.字符串旋转和手摇算法
《编程珠玑》里的一个题目：
请将一个具有n个元素的一维向量x向左旋转i个位置。例如，假设n=8，i=3，
那么向量abcdefgh旋转之后得到向量defghabc。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
/**
* 用于反转字符数组中index1~index2位置的这一段
* 左闭右开区间,index1<=下标<index2
*/
public
static
void
reverse(
char
[] chr,
int
index1,
int
index2){
if
(index2-index1 <
2
)
return
;
int
j=index2-
1
;
//右侧下标
for
(
int
i=index1;i<(index2+index1)/
2
;i++){
swap(chr,i,j--);
}
}
/**
* 旋转
* 使用三次反转，实现旋转
* 数组注意区间取值
* @param m 从位置m处进行旋转
*/
public
static
void
rotation(
char
[] chr,
int
m){
//第一次倒置0~m位置
reverse(chr,
0
,m);
//第二次倒置m~最后位置
reverse(chr,m,chr.length);
//最后整体倒置
reverse(chr,
0
,chr.length);
}
private
static
void
swap(
char
[] arr,
int
index1,
int
index2){
char
temp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
|
手摇算法还可以用来优化归并排序，实现不需要额外空间开销的原地归并，即将空间复杂度降为O（1），下次再去看一下。
本文转自邴越博客园博客，原文链接：http://www.cnblogs.com/binyue/p/5194462.html，如需转载请自行联系原作者
