算法-三向字符串快速排序

  1. 云栖社区>
  2. 博客>
  3. 正文

算法-三向字符串快速排序

文艺小青年 2017-07-06 11:27:00 浏览740
展开阅读全文

根据高位优先的字符串排序的思想我们可以改进快速排序算法,根据键的首字母进行三向切分,将两者结合起来就是可以理解的高效排序算法-三向字符串快速排序。三向字符串快速排序是一个字符串排序的通用算法,最多的情况适用于含有公共前缀的字符串。

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,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
文艺小青年
+ 关注