为什么要将插入排序和希尔排序放在一起来写呢？因为插入排序和希尔排序的思路是相同的，希尔排序可以看成是插入排序的特殊情况，下面就来详细说说两者的思路。
1. 插入排序
插入排序原理：每次将无序序列中的首个元素在已排序序列中从后向前扫描，按照给定规律找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。
1.1 第一次排序
假设下面存在一组无序数列[9,7,3,3,6,2,1,4,10]，需要通过插入排序将其变为[1,2,3,3,4,6,7,9,10]。
先通过插入排序分析第一次排序是怎么个过程。
- 分为左右两部分，左边为0号索引位置元素9【假设为有序序列】，右边为(1,n-1)索引位置的元素【假设为无序序列】，每次都拿右边首个元素与左边的元素进行对比【第一次排序下为1索引位置元素】，按照规律插入到左边有序序列对应位置中。
- 有序序列部分元素为9，无序序列部分首元素为7，7比9小，所以交换彼此的位置，将7插入到9前面，则7和9的序列就已经确定。第一轮排序结束后，有序序列部分元素有7、9，无序序列部分从索引2开始到n-1
- 根据以上原理和图解，可以完成以下代码
"""第一次插入排序"""
def insert_sort(target_list):
i = 1 # 右边无序序列的首个元素索引
# 后面元素比前面元素小，交换两个元素位置
if target_list[i] < target_list[i-1]:
target_list[i],target_list[i-1] = target_list[i-1],target_list[i]
1.2 第二次排序
- 右边无序部分首个元素【此时为2索引位置元素3】，依次与左边有序部分每个元素进行对比，如果比左边的元素小，则交换彼此的位置
- 3先跟9对比，比9小，则交换彼此位置【此时左边是7 3 9】，再跟7对比，比7小，交换彼此位置【此时是 3 7 9】
- 假设3所对应的游标是i，可以看出i不断的往前移动，即每次比较i都要往左移动一个单位【i -= 1】
1.3 第n次排序
- 由于需要对 右边无序列表的每一个元素都与左边进行对比，起使时默认0号元素为有序列表，因此无序列表的索引位置为(1,n-1)，用j表示每次循环时右边无序列表首位的索引位置，而range()函数左闭右开，因此代码为for j in range(1,n)
- 由于i游标每次都需要往左移动一个单位，不断与前一个元素对比，直到插入到正确的位置，因此移动条件为while i >0,当target_list[i]比前target_list[i-1]大的时候停止移动
def insert_sort(alist):
"""插入算法"""
n = len(alist)
# 从右边的无序序列中取出多少个元素执行这样的过程
for j in range(1,n):
i = j
# 循环条件为i>0,因为需要与左边有序列表的每个元素进行比较，一直移动到0号索引位置
while i>0:
if alist[i] < alist[i-1]:
alist[i],alist[i-1] = alist[i-1],alist[i]
i -= 1
else:
# 如果alist[i]位置的元素比alist[i-1]大，说明已经到了指定位置，则退出循环
break
2. 希尔排序
- 希尔排序可以看成插入排序的改进版，原理与插入排序类似
- 将数组视为很多个无序的序列，先确定一个间隔gap，以gap为单位，每个元素与其索引+gap位置的元素组成一个序列，使用插入算法的思想进行排序
- 缩小gap的值，重复上述步骤
-
当gap缩小到1时，即为插入排序
2.1 第一次排序
排序思路图
第一次排序完成图
假设gap取值为n/2,则可将上述数组分为如上图所示4组无序数列，对每组无序数列都使用插入算法后，数组的顺序变为[6 2 1 3 9 7 3 4 10]
gap减少为原gap值得一半 即 gap //= 2
每一个使用gap分离后得数组，按照插入排序得思想，其右边无序列表得第一个元素所对应得索引位置为gap
2.2 第二次排序
- 经过第一次排序后，数组元素顺序变为[6,2,1,3,9,7,3,4,10]
- gap缩小为2
-
实现变化后的数组和缩小后的gap重复第一步步骤
第二次排序思路图
第二次排序完成图
2.3 第n次排序
- 第二次排序完成后，数组变为 1 2 3 4 6 4 9 7 10
- gap继续缩小为原来得一半，然后执行下一次排序
- 直到gap=1时，为最后一次排序，此时相当于插入排序
- 代码实现【只需要将插入排序得步长和无序列表起始位置改为gap；添加gap长度变化的规则即可】
def shell_sort(target_list):
n = len(target_list)
gap = n // 2
# 当gap>=1时循环进行
while gap >= 1:
# j 代表右边无序列表得起始位置
for j in range(gap,n):
i = j
while i > 0:
if target_list[i] < target_list[i-gap]:
target_list[i],target_list[i-gap] = target_list[i-gap],target_list[i]
else:
break
# 每次gap缩小为原来得一半
gap //= 2
