def main(array):
    """
    希尔排序
        -------------------------------- len = 10
        5, 3, 9, 12, 6, 1, 7, 2, 4, 11
        len / 2 = 5 步长是5
        --------------------------------索引5开始 与5-len/2相比
        , 3, 9, 12, 6, , 7, 2, 4, 11    
        5              1
        --------------------------------使用插入排序进行排序
        1, 3, 9, 12, 6, 5, 7, 2, 4, 11  
        --------------------------------
        #1, , 9, 12, 6, 5, , 2, 4, 11
        #   3              7
        #--------------------------------不变，这一步在遍历时就不会走
        1, 3, , 12, 6, 5, 7, , 4, 11
              9              2
        --------------------------------使用插入排序进行排序
        1, 3, 2, 12, 6, 5, 7, 9, 4, 11
        --------------------------------
        1, 3, 2, , 6, 5, 7, 9, , 11
                 12            4
        --------------------------------使用插入排序进行排序
        1, 3, 2, 4, 6, 5, 7, 9, 12, 11
        # 6 和 11 不走
        5 // 2 = 2 步长是2
        --------------------------------
        索引2开始，1-2跳过
        索引3，3-4跳过
        索引4，1-2-6跳过
        索引5，3-4-5跳过
        索引6，1-2-6-7跳过
        索引7，3-4-5-9跳过
        索引8，1-2-6-7-12跳过
        索引9，3-4-5-9-11跳过
        --------------------------------
        2 // 2 = 1
        1, 3, 2, 4, 6, 5, 7, 9, 12, 11
        --------------------------------
        索引1开始，1-3跳过
        索引2
         ,  ,  , 4, 6, 5, 7, 9, 12, 11
        1, 3, 2
        --------------------------------3右移，2补进去
        1, 2, 3, 4, 6, 5, 7, 9, 12, 11
        索引3，1-2-3-4跳过
        索引4，1-2-3-4-6跳过
        索引5
        1, 2, 3, 4, 6, 5, 7, 9, 12, 11
        1, 2, 3, 4, 6, 5
        --------------------------------6右移，5补进去
        1, 2, 3, 4, 5, 6, 7, 9, 12, 11
        --------------------------------
        ........
        --------------------------------
        12右移，11补进去
        1, 2, 3, 4, 5, 6, 7, 9, 11, 12
    """
    d = len(array)
    while d > 1:
        d = d // 2
        for i in range(d, len(array)):
            insert_vdue = array[i]
            while i > 0 and i - d >= 0 and insert_vdue < array[i - d]:
                array[i] = array[i - d]
                i -= d
            array[i] = insert_vdue
    return array


array = [5, 3, 9, 12, 6, 1, 7, 2, 4, 11]
print(main(array))