"""
希尔排序：也称递减递增排序，它将原始集合分为多个较小的子集合，然后对每个集合
运用插入排序
1. 当增量为3时，表示每相隔两个的元素（索引差3）为一个子序列，将原序列分为了三组子序列
2. 对每个子序列使用插入排序，此时每个子序列就是有序的
3. 逐渐减小增量，重复第二2步
4. 当增量为1时，再执行一次插入排序，此时完整序列就是有序的

希尔排序的复杂度分析稍微复杂一些，但其大致分布在 O(n) 到 O(n^2) 之间。
"""


def shell_sort(nums: list[int]):
    step = len(nums) >> 1
    while step >= 1:
        # 分成了 step 个子序列，循环 step 次，对每个子序列使用插排
        for i in range(step):
            for j in range(i + step, len(nums), step):
                pos = j
                cur = nums[j]
                # 无法对子序列使用二分查找，查找插入位置，因为中间位置无法确定
                while pos >= step and cur < nums[pos - step]:
                    # 将比当前值大的往后移 step 位
                    nums[pos] = nums[pos - step]
                    pos -= step

                nums[pos] = cur
        step >>= 1


nums = [47, 29, 71, 99, 78, 19, 24, 47]
shell_sort(nums)
print(nums)