与之前的低位优先的字符串排序不同，低位优先是从右向左开始排序，高位优先是从左向右开始排序，高位优先排序的过程是字符串切分为独立排序的子数组完成排序任务，切分会为每个首字母得到一个子数组，低位优先排序适用于定长字符串的排序，高位优先适用于随机字符串排序，主要实现过程比低位多了一步，就是递归排序.
|
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
static
int
R=26;
@implementation MSD
-(NSInteger)charAt:(NSString *)str index:(NSInteger)index{
if
(index<str.length) {
return
[str characterAtIndex:index]-97;
}
else
{
return
-1;
}
}
-(
void
)setupData:(NSMutableArray *)dataSource{
NSInteger count=[dataSource count];
self.tempArr=[[NSMutableArray alloc]initWithCapacity:1];
for
(NSInteger i=0; i<count; i++) {
[self.tempArr addObject:[NSNull
null
]];
}
[self sort:dataSource low:0 high:count-1 index:0];
}
-(
void
)sort:(NSMutableArray *)dataSource low:(NSInteger)low high:(NSInteger)high index:(NSInteger)index{
if
(high<=low) {
return
;
}
NSMutableArray *count=[[NSMutableArray alloc]initWithCapacity:1];
for
(NSInteger i=0; i<R+2; i++) {
[count addObject:[NSNumber numberWithInteger:0]];
}
//统计频率
for
(NSInteger i=low; i<=high; i++) {
NSInteger charValue=[self charAt:dataSource[i] index:index];
count[charValue+2]=[NSNumber numberWithInteger:[count[charValue+2] integerValue]+1];
}
for
(NSInteger j=0; j<R+1; j++) {
count[j+1]=[NSNumber numberWithInteger:[count[j] integerValue]+[count[j+1] integerValue]];
}
//将元素从上到下分类
for
(NSInteger m=low; m<=high; m++) {
NSInteger tempIndex=[count[[self charAt:dataSource[m] index:index]+1] integerValue];
self.tempArr[tempIndex]=dataSource[m];
count[[self charAt:dataSource[m] index:index]+1]=[NSNumber numberWithInteger:tempIndex+1];
}
//重新排序赋值
for
(NSInteger i=low; i<=high; i++) {
dataSource[i]=self.tempArr[i-low];
}
//递归循环
for
(NSInteger r=0;r<R;r++) {
[self sort:dataSource low:low+[count[r] integerValue] high:low+[count[r+1] integerValue]-1 index:index+1];
}
}
@end
|
代码测试:
|
1
2
3
4
5
6
|
MSD *msd=[[MSD alloc]init];
NSMutableArray *dataSource=[[NSMutableArray alloc]initWithObjects:
@"she"
,
@"girl"
,
@"he"
,
@"by"
,
@"keso"
,
@"fly"
,
@"elephant"
,
@"the"
,
@"shells"
,
@"she"
,
@"sells"
,
@"are"
,
@"boy"
,
@"seachells"
,nil];
[msd setupData:dataSource];
[dataSource enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
NSLog(
@"%@"
,obj);
}];
|
测试效果:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4857130.html，如需转载请自行联系原作者
