转载

算法-高位优先的字符串排序

与之前的低位优先的字符串排序不同，低位优先是从右向左开始排序，高位优先是从左向右开始排序，高位优先排序的过程是字符串切分为独立排序的子数组完成排序任务，切分会为每个首字母得到一个子数组，低位优先排序适用于定长字符串的排序，高位优先适用于随机字符串排序，主要实现过程比低位多了一步，就是递归排序.

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

代码测试:

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);         }];

测试效果:

算法-高位优先的字符串排序