"""
希尔排序
    希尔排序（Shell Sort）是插入排序的一种。是针对直接插入排序算法的改进。
    该方法又成缩小增量排序，因DL.Shell于1959年提出而得名。
    希尔排序属于插入类排序，是将整个无序列分割成若干个小的子序列分别进行插入排序。

算法描述：
    先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；
    然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序即可。

过程举例：
    假设待排序文件有10个记录，其关键字分别是：
    49, 38, 65, 97, 76, 13, 27, 49, 55, 04
    增量序列d的取值依次为：
    5, 3, 1

    d=5
    49 38 65 97 76 13 27 49 55 04
    49 13
    |------------------------------------|
    38 27
    |------------------------------------|
    65 49
    |------------------------------------|
    97 55
    |------------------------------------|
    76 04
    |------------------------------------|
    一趟结果
    13 27 49 55 04 49 38 65 97 76
    -----------------------------------------------------------------------------

    d=3
    13 27 49 55 04 49 38 65 97 76
    13 55 38 76
    |-----------|-----------|------------|
    27 04 65
    |-----------|-----------|------------|
    49 49 97
    |-----------|-----------|------------|
    二趟结果
    13 04 49 38 27 49 55 65 97 76
    -----------------------------------------------------------------------------

    d=1
    13 04 49 38 27 49 55 65 97 76
    |----|-----|-----|-----|-----|
    三趟结果
    04 13 27 38 49 49 55 65 76 97
    -----------------------------------------------------------------------------

可以看到示例代码与直接插入排序极为相似。
希尔排序的增量d选取有很多方法，示例代码就是取d=n/2；然后去d=d/2一直到d=1。
或许这不是最优的增量序列，但却是最简单的。

刚开始时，d最大，每一组的元素个数很少，排序速度很快；
d变小时，每一组元素变多，但元素基本有序了，插入排序对于有序的序列效率很高。
所以，希尔排序的时间复杂度会比直接插入排序好。
然而，在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性会被打乱，因而shell排序是不稳定的。

希尔排序是高级排序算法中最容易实现的，效率也不赖。考试或比赛时若需要排序，这是不错的选择。
"""


def shell(a):
    n = len(a)  # 数组长度
    k = int(n / 2)
    while k > 0:
        # 通过k对待排序元素进行分组
        for i in range(k, n):
            t = a[i]
            j = i - k
            # 使用直接插入排序
            while j >= 0 and a[j] > t:
                a[j + k] = a[j]
                j -= k
            a[j + k] = t
        k = int(k / 2)


a = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
print(f'排序前:{a}')
shell(a)
print(f'排序后:{a}')
