1.简单插入排序存在的问题：
数组arr={2,3,4,5,6,1}这时需要插入的数1(最小)。
这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论:当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响
2.介绍: 希尔排序是希尔（DonaldShell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
3.基本思想: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
4.希尔排序示意图
希尔排序示意图
5.代码实现
希尔排序交换法
#希尔排序交换法
import random
import time
def sorted(sortlist):
listlength = len(sortlist)
gap = int(listlength / 2)
while (gap >0):
for i in range(gap,listlength):
j = i
while (j-gap>=0) and (sortlist[j] < sortlist[j-gap]):
sortlist[j],sortlist[j-gap] = sortlist[j-gap],sortlist[j]
j =j - gap
gap = int(gap/2)
print(sortlist)
l = [8,9,1,7,2,3,5,4,6,0]
sorted(l)
# 3 5 1 6 0 8 9 4 7 2
# 0 2 1 4 3 5 7 6 9 8
# 0 1 2 3 4 5 6 7 8 9
def shellSort(sortlist):
listlength = len(sortlist)
gap = int(listlength/2)
while gap > 0:
for i in range(gap,listlength):
temp = sortlist[i]
j = i
while j >= gap and sortlist[j-gap] >temp:
sortlist[j] = sortlist[j-gap]
j -= gap
sortlist[j] = temp
gap = int(gap/2)
print(sortlist)
sortlist = [8,9,1,7,2,3,5,4,6,0]
shellSort(sortlist)
希尔排序插入法
def shell_sort(arr):
"""希尔插入排序"""
# 取整计算增量（间隔）值
gap = len(arr) // 2
while gap > 0:
# 从增量值开始遍历比较
for i in range(gap, len(arr)):
j = i
current = arr[i]
# 元素与他同组的前面的每个元素进行比较，如果该元素比前面的小则 前面的替换掉该元素，替换完后最前面的位置就是该元素最终位置
while j - gap >= 0 and current < arr[j - gap]:
arr[j] = arr[j - gap]
j -= gap
# print("1",arr)
arr[j] = current
print("2",arr)
# 缩小增量（间隔）值
gap //= 2
return arr
res = shell_sort([1,9,8,7,2,3,5,4,6,0] )
print(res)
#1, 5, 4, 6, 0, 3, 9, 8, 7, 2
#0, 2, 1, 3, 4, 5, 7, 6, 9, 8
#0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
