排序算法（三）：希尔排序

希尔排序是插入排序的升级版，回忆插入排序，当拿到一张新的扑克牌，我们需要拿着它逐一与手中的牌比较。当这张新的扑克牌恰好是最小的，那意味着手里有多少张牌就要移动多少次，所以插入排序的时间复杂度跟原数组的有序程度紧密相连。

为了提高插入排序的效率，算法专家考虑是否能先把数组变得相对有序一些，尽量先把数组中较大的和较小的分别放置在数组的末尾和开头，这样比较的次数就会下降很多。

# Python program for implementation of Shell Sort 
  
def shellSort(arr): 
  
    n = len(arr) 
    gap = n // 2  # 初始化间隔，间隔的取舍没有确切的规定
  
    while gap > 0: 
  
        for i in range(gap, n):  # 索引从间隔（gap）-->数组的末尾（n）
  
            new_card = arr[i]    # 手中的扑克牌
  
            j = i - gap          # 索引间隔gap左侧的元素
            while j >= 0 and arr[j] > new_card:  # 当左侧的元素大于手中的扑克牌
                arr[j + gap] = arr[j]            # 将较大的元素放在i=j+gap的位置
                j -= gap 
  
            arr[j + gap] = new_card  # gap左侧的元素遍历完了，将手中的扑克牌放在j+gap的位置，同插入排序  
        gap //= 2

对比插入排序，其实代码的差别不大，只不过把代码中的1换成了gap：

def insert_sort(array):
    for i in range(1, len(array)):
        new_card = array[i]  # 手中的牌
        j = i - 1
        while j >= 0 and new_card < array[j]:  # 新摸到的牌如果大于手中的牌则往后移动
            array[j+1] = array[j]
            j -= 1
        array[j+1] = new_card
    return array