希尔排序

将数组按一定间隔分割成若干个子数组，然后每个子数组分别进行插入排序，接着缩小间隔继续，一直循环下去直到排序完成。

实践

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def ShellSort(nums):
	gap = len(nums) // 2 # 先确定一个间隔数(两两一组)
	# 按照 gap 分组
	while gap > 0:
		# 对每组元素进行插入排序
		for i in range(gap, len(nums)):
			base = nums[i]
			j = i - gap
			while j >= 0 and nums[j] > base:
				nums[j + gap] = nums[j]
				j -= gap
			nums[j+gap] = base
		# 缩小 gap 间隔
		gap = gap // 2
	return nums

# 测试
sort.test(ShellSort)