希尔排序

希尔排序是插入排序的一种，也称为缩小增量排序。是直接插入排序的一种更高效的改进版本。基本思想如下：
先将整个待排序列分成若干个子序列，分别进行直接插入排序，等到整个序列中的记录“基本有序”了，再对全体记录进行一次直接插入排序。

算法实现：
我们这里简单处理增量序列： 增量序列d={n/2,n/4,n/8.....1} n为序列元素个数。
即：先将要排序的一组记录，按照某个增量d分成若干组 子序列，每组中记录的下标 相差d。对每组中的全部元素进行直接插入排序，然后再用一个较小的增量(d/2)对它进行分组，再每组进行直接插入排序。连续不断缩小增量直至为1，最后使用直接插入排序完成排序。
代码如下：

- (void) shellSort{
    long d = _array.count / 2;
    while (d >= 1) {
        [self shellInsertSort:_array and:d];
        d = d / 2;
    }
}

- (void)shellInsertSort:(NSMutableArray *)array and:(long)d{
    for(NSInteger i = d ; i < array.count; i++){
        if(array[i] < array[i-d]){
            NSInteger j = i-d;
            NSInteger tmp = [array[i] intValue];
            [array replaceObjectAtIndex:i withObject:array[i-d]];
            
            while (j > -1&&tmp < [array[j] intValue]) {
                [array replaceObjectAtIndex:j+d withObject:array[j]];
                j = j - d;
            }
            [array replaceObjectAtIndex:j+d withObject:@(tmp)];
        }
    }
}