根据高位优先的字符串排序的思想我们可以改进快速排序算法，根据键的首字母进行三向切分，将两者结合起来就是可以理解的高效排序算法-三向字符串快速排序。三向字符串快速排序是一个字符串排序的通用算法，最多的情况适用于含有公共前缀的字符串。
|
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，如需转载请自行联系原作者