算法-三向字符串快速排序
根据高位优先的字符串排序的思想我们可以改进快速排序算法，根据键的首字母进行三向切分，将两者结合起来就是可以理解的高效排序算法-三向字符串快速排序。三向字符串快速排序是一个字符串排序的通用算法，最多的情况适用于含有公共前缀的字符串。
|
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
34
35
36
37
38
39
40
41
|
-(NSInteger)charAt:(NSString *)str index:(NSInteger)index{
if
(index<str.length) {
return
[str characterAtIndex:index]-97;
}
else
{
return
-1;
}
}
-(
void
)exchange:(NSMutableArray *)dataSource first:(NSInteger)first second:(NSInteger)second{
NSString *temp=dataSource[first];
dataSource[first]=dataSource[second];
dataSource[second]=temp;
}
-(
void
)sort:(NSMutableArray *)dataSource{
[self sort:dataSource low:0 high:[dataSource count]-1 index:0];
}
-(
void
)sort:(NSMutableArray *)dataSource low:(NSInteger)low high:(NSInteger)high index:(NSInteger)index{
if
(high<=low) {
return
;
}
NSInteger left=low,right=high;
NSInteger middle=[self charAt:dataSource[low] index:index];
NSInteger i=low+1;
while
(i<=right) {
NSInteger t=[self charAt:dataSource[i] index:index];
if
(t<middle) {
[self exchange:dataSource first:left++ second:i++];
}
else
if
(t>middle){
[self exchange:dataSource first:i second:right--];
}
else
{
i++;
}
}
[self sort:dataSource low:low high:left-1 index:index];
if
(middle>=0) {
[self sort:dataSource low:left high:right index:index+1];
}
[self sort:dataSource low:right+1 high:high index:index];
}
|
代码测试:
|
1
2
3
4
5
6
7
8
|
Quick3String *quick=[[Quick3String alloc]init];
NSMutableArray *dataSource=[[NSMutableArray alloc]initWithObjects:
@"xiang"
,
@"girl"
,
@"he"
,
@"fei"
,
@"keso"
,
@"fly"
,
@"elephant"
,
@"de"
,
@""
,
@"she"
,
@"elephant"
,nil];
[quick sort:dataSource];
[dataSource enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
NSLog(
@"%@"
,obj);
}];
NSLog(
@"技术交流群:%@"
,
@"228407086"
);
NSLog(
@"博客园-FlyElephant:http://www.cnblogs.com/xiaofeixiang"
);
|
测试效果:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4857404.html，如需转载请自行联系原作者