思路
开始的时候逐渐让数组变得基本有序，最后使用一次使用「插入排序」就变得高效了。
- 「逐渐让数组变得基本有序」的方法是让移动的「步幅」增大，不是一步一步挪过去，而是「大步流星」、「连蹦带跳」走过去；
- 「逐渐缩小增量」「分组实施插入排序让数组变得逐渐接近有序」「最后执行一次标准的插入排序」（ 最后一轮就是「原汁原味」的插入排序。
动态演示
视频： https://www.bilibili.com/video/av64424835/
边想边写
- 获取数组长度，求出第一次「步长」
def shell_sort(nums):
length = len(nums)
gap = length // 2
# ...
- 遍历数组，并比较
def shell_sort(nums):
length = len(nums)
gap = length // 2
for i in range(length):
# 越界则退出循环
if i + gap >= length:
break
if nums[i] > nums[i+gap]:
nums[i], nums[i+gap] = nums[i+gap], nums[i]
- 上方只是完成了一次「步长」的比较，我们需要让步长一直到除到1才能结束
def shell_sort(nums):
length = len(nums)
gap = length // 2
while gap > 0:
for i in range(length):
if i + gap >= length:
break
if nums[i] > nums[i + gap]:
nums[i], nums[i + gap] = nums[i + gap], nums[i]
gap = gap // 2
return nums
当最后
gap=1时，其实就是执行了一次 「插入排序」
完整代码
def shell_sort(nums):
length = len(nums)
gap = length // 2
while gap > 0:
for i in range(length):
if i + gap >= length:
break
if nums[i] > nums[i + gap]:
nums[i], nums[i + gap] = nums[i + gap], nums[i]
gap = gap // 2
return nums
用例测试
测试用例： https://leetcode-cn.com/submissions/detail/89203696/testcase/
使用此算法，用时：0.1754603385925293
和「选择排序相比」，效率大大提高
与「插入排序」对比
5000个随机数 「数组」的排序耗时：
shell_sort time: 0.020738601684570312
insert_sort time: 0.8852617740631104
5000个随机数 「“几乎有序”数组」的排序耗时：
shell_sort time: 0.0062313079833984375
insert_sort time: 0.0076389312744140625
至此，我们大致看出，对杂乱的情况排序，「希尔排序」更快，而这其中的主要原因就是 插入排序更擅长 “几乎有序”的数组， 在 “几乎有序”的数组排序中，「希尔」与「插入」相差无几
时间复杂度
- 时间复杂度：O(n(1.3—2))，希尔排序是非稳定的排序方法，最坏的情况与「插入排序」一样是 O(n^2)