希尔排序（Shell Sort）

1. 算法描述

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

• 先取一个整数increment（小于数组长度）作为间隔将全部元素分为increment个子序列;
• 然后分别对每一个子序列进行插入排序；
• 当increment为1时,只剩一个序列,进行插入排序,完成排序;

2. 过程演示

希尔排序.gif

原始数据

34 54  12  78 3  45  9           


increment = length / 2;
increment = 7 /2;
increment = 3;

34  78    9         

54  3               

12 45                 


I = 3;

34 54  12  78 3  45  9         (34 78  9)

I = 4;  

34  54  12  78  54  45  9     
34    3  12  78  54  45  9        (3  54)

I = 5
  
34 3  12  78  54  45  9         (12  45)

I =  6 

34  54  12 78  3  45  78
34  54  12 34  3  45  78  
9    54  12 34  3  45  78        (9  34 78 )



increment = 1;

9  54  12 34 3  45  78 

I = 1;

9  54  12 34 3  45  78 

I = 2

9  54  54 34 3  45  78 
9  12  54 34 3  45  78 

I = 3

9 12 54 54 3  45  78 
9 12  34 54 3  45  78 

I = 4

9 12  34 54 54  45  78 

9 12  34 34 54  45  78 

9 12 12  34 54  45  78 

9  9 12  34 54  45  78 

3 9 12  34 54  45  78 

I = 5

3 9 12  34 54 54  78 

3 9 12  34 45 54  78 

I = 6
3 9 12  34 45 54  78 

3. 代码实现

- (NSArray *)shellSort:(NSArray *)sortArray {
    NSMutableArray *sort = [NSMutableArray arrayWithArray:sortArray];
    NSInteger length = sortArray.count;

    NSInteger count1 = 0;// 外层循环次数
    NSInteger count2 = 0;//内层循环次数

    //初始增量为数组长度的一半，然后每次除以2取整
    for (NSInteger increment = length/2; increment > 0; increment /=2) {
        //初始下标设为第一个增量的位置，然后递增
        count1 ++;
        for (NSInteger i = increment; i < length; i++) {
            // 跳跃式  插入排序
            NSInteger preIndex = i - increment;
            NSInteger currentValue = [sort[i] integerValue];
            //然后将此位置之前的元素，按照增量进行跳跃式比较
            while (preIndex >= 0  && currentValue < [sort[preIndex] integerValue]) {
                sort[preIndex + increment] = sort[preIndex];
                preIndex -= increment;
                count2 ++;
            }
            sort[preIndex + increment] = @(currentValue);
        }
    }
    NSLog(@"count1 : %ld\n count2 :%ld\n sort: %@",(long)count1,(long)count2,sort);
    return sort;
}

4. 验证

NSArray *arr = [self pakageNumber:1000];  // 1000个随机数
NSArray *arr1 = [self selectedSort:arr];
count1  :9                        // 外层循环
count2 :8006                  // 中层循环
count3 :7272                  // 内层循环

一万条数据所用时间
time:0.038147s;