转载

算法-希尔排序

希尔排序实际上是插入排序的一种，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。时间复杂度无法准确的估计，希尔排序的基本逻辑记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。

-(NSMutableArray *)shellSort:(NSMutableArray *)arr{  NSInteger  group=1;  while (group>[arr count]/3) {   group=3*group+1;  }  while (group>=1) {   //将数组变成group有序   for (NSInteger i=group; i<[arr count]; i++) {    //将分组后的数据与前面的数据一一比较进行交换    for (NSInteger j=i; j>=group&&[arr[j] integerValue]<[arr[j-group] integerValue]; j-=group) {     NSInteger temp=[arr[j] integerValue];     arr[j]=[NSNumber numberWithInteger:[arr[j-group] integerValue]];     arr[j-group]=[NSNumber numberWithInteger:temp];    }   }   group=group/3;  }    return arr; }

如果数组的长度是10，这里的增量是4，网上有些博客对理解是，增量的取值规则为第一次取总长度的一半,第二次取一半的一半,依次累推直到1为止,其实这样可以快速理解希尔排序，不过希尔排序的性能跟增量的选择有很大的关系，对于增量的选择不应该不应该这么简单粗暴，如果在实际实战过程中需要根据实际情况取决。

NSMutableArray *arr=[[NSMutableArray alloc]initWithCapacity:10]; [arr addObject:@"6"]; [arr addObject:@"3"]; [arr addObject:@"2"]; [arr addObject:@"8"]; [arr addObject:@"9"]; [arr addObject:@"10"]; [arr addObject:@"4"]; [arr addObject:@"5"]; [arr addObject:@"1"]; MySort  *sort=[[MySort alloc]init]; NSMutableArray  *resultArr= [sort shellSort1:arr]; for (NSInteger i=0; i<[resultArr count]; i++) {     NSLog(@"%@",[resultArr objectAtIndex:i]); } NSLog(@"iOS技术交流群:228407086"); NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");

运行结果:

算法-希尔排序