简述：引入gap概念，分块进行插入排序。gap会根据要求递减，当 gap == 1 等于1时，为基本的插入排序。

• 最优时间复杂度：根据步长序列的不同而不同
• 最坏时间复杂度：O(n2)
• 稳定型：不稳定

python3

# coding: utf-8

def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    gap = n // 2

    while gap > 0:
        for j in range(gap,n):
            i = j
            while i > 0:
                if j >= gap and alist[i] < alist[i - gap]:
                    alist[i], alist[i - gap] = alist[i - gap], alist[i]
                    i -= gap
                else:
                    break
        gap //= 2

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    shell_sort(li)
    print(li)

/**
 希尔算法
 */
- (void)shell_sort:(NSMutableArray *)arr {
    
    NSInteger gap = arr.count / 2;
    
    while (gap >= 1) {
        for (NSInteger i = gap; i < arr.count; i++) {
            NSInteger j = i;
            while (j > 0) {
                if (j >= gap && arr[j] < arr[j - gap]) {
                    NSNumber *temp = arr[j];
                    arr[j] = arr[j - gap];
                    arr[j - gap] = temp;
                    j -= gap;
                } else {
                    break;
                }
            }
        }
        // 缩短步长
        gap = gap / 2;
    }
}