算法-希尔排序

xiaofeixiang 2021-08-04 原文

希尔排序实际上是插入排序的一种，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。时间复杂度无法准确的估计，希尔排序的基本逻辑记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至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");

　运行结果: