希尔排序是对插入排序的优化。
插入排序在数据集”基本有序“时，效率最高，因此，希尔排序的优化思路便是先把数据集变成”基本有序“， 再进行插入排序。
那么如何变成”基本有序“？
1、对列表按一定的间隔(gap)进行分组，公式：gap = length / 2
如 list_datas = [88, 6, 57, 72, 60, 42, 83, 73, 48, 85]
因为 gap = 5，
那么 88，42为一组，
6，83为一组，
57，73为一组，
72，48为一组，
60, 85为一组
注意这里只是”逻辑分组“，并没有改变它们在列表中的位置
2、分别对每个分组进行排序调整，调整完毕后，gap //= 2, 然后再重复进行 1 操作，
当 gap = 1 时，便实现整个列表”基本有序“，此时再进行插入排序，完成整个希尔排序
时间复杂度：
思路一：
1、对每个分组进行排序，因为每个分组都只有两个数，因此，直接进行判断，然后调换顺序
2、gap // = 2, 重复1操作直至 gap == 1, 此时对整个列表进行插入排序
def shell_sort1(datas):
length = len(datas)
gap = length // 2
while gap > 1:
for index in range(0, length - gap):
if datas[index] > datas[index + gap]:
temp = datas[index]
datas[index] = datas[index + gap]
datas[index + gap] = temp
gap //= 2
for index in range(0, length):
pre_index = index - 1
current = datas[index]
while pre_index >= 0 and datas[pre_index] > current:
datas[pre_index + 1] = datas[pre_index]
pre_index -= 1
datas[pre_index + 1] = current
return datas
思路二：
对每个分组进行排序时，可以直接使用插入排序。
问题：每个分组的数字，都不相邻，如何进行类似 pre_index + 1 的操作?
答： 把 pre_index + 1 改成 pre_index + gap 就行了 (又是一个数学思维)
这样，给分组进行排序 和 最终整个列表的排序 都可以使用插入排序，代码可以复用，空间复杂度就降低了
def shell_sort2(datas):
length = len(datas)
gap = length // 2
while gap >= 1:
for end_index in range(0, length - gap, gap):
pre_index = end_index
current = datas[end_index + gap]
while pre_index >= 0 and datas[pre_index] > current:
datas[pre_index + gap] = datas[pre_index]
pre_index -= gap
datas[pre_index + gap] = current
gap //= 2
return datas