希尔排序

简述

希尔排序法致力于避免插入排序中大量的比较和元素移动，主要思想就是通过对待排序集合按某一增量进行跳跃式排序，然后不断调整增量逐步对集合完成排序。

示例代码

Python

from random import randint
from typing import List

def random_list(length: int = 10, start: int = 10, end: int = 100) -> List[int]:
    """生成指定长度的随机整数列表

    Args:
        length (int, optional): 随机数列表长度. Defaults to 10.
        start (int, optional): 范围最小值. Defaults to 10.
        end (int, optional): 范围最大值. Defaults to 100.

    Returns:
        List[int]: 随机数列表
    """
    return [randint(start, end) for _ in range(length)]

def shell_sort(nums):
    lens = len(nums)
    gap = 1  
    while gap < lens // 3:
        gap = gap * 3 + 1  # 动态定义间隔序列
    while gap > 0:
        for i in range(gap, lens):
            curNum, preIndex = nums[i], i - gap  # curNum 保存当前待插入的数
            while preIndex >= 0 and curNum < nums[preIndex]:
                nums[preIndex + gap] = nums[preIndex] # 将比 curNum 大的元素向后移动
                preIndex -= gap
            nums[preIndex + gap] = curNum  # 待插入的数的正确位置
        gap //= 3  # 下一个动态间隔
    return nums

if __name__ == "__main__":
    origin_nums = random_list(100*100)
    print(origin_nums)
    print(shell_sort(origin_nums))