我们之前学过插入排序，它在数组大部分元素已经有序时效率很高，但如果数组完全无序或者逆序，每次只能移动一个元素，效率就比较低。希尔排序（Shell Sort）是插入排序的改进版，它通过分组的方式，让数组先变得基本有序，再用插入排序处理，从而提高效率。
希尔排序的基本思想¶
希尔排序的核心是“分组”和“插入排序”。它不像插入排序那样只比较相邻元素，而是将数组分成若干组，每组内的元素间隔一定的距离（这个距离称为“增量”或“步长”），然后对每组内的元素进行插入排序。随着增量逐渐减小，分组越来越细，直到增量为1时，整个数组已经基本有序，此时插入排序就能快速完成。
希尔排序的步骤¶
- 选择初始增量：通常初始增量取数组长度的一半（
n//2），然后每次将增量减半，直到增量为0。 - 分组与插入排序：对于每个增量
gap，数组被分成gap个“组”，每个组内的元素下标相差gap。例如，数组长度为10，gap=3时，组1是下标0、3、6、9，组2是下标1、4、7，组3是下标2、5、8。然后对每组内的元素进行插入排序。 - 重复调整增量：当增量减小到1时，整个数组已基本有序，此时插入排序能快速完成。
代码实现（Python）¶
def shell_sort(arr):
n = len(arr)
gap = n // 2 # 初始增量为数组长度的一半
while gap > 0:
# 遍历每个组内的元素
for i in range(gap, n):
temp = arr[i] # 保存当前元素，避免被覆盖
j = i - gap # 组内前一个元素的下标
# 将前面比temp大的元素后移
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j] # 后移一位
j -= gap # 继续向前比较
arr[j + gap] = temp # 将temp插入到正确位置
gap = gap // 2 # 增量减半，逐步缩小
return arr
代码解释：
- n = len(arr)：获取数组长度，用于计算初始增量。
- gap = n // 2：初始增量为数组长度的一半，这是最常用的简单增量方式。
- while gap > 0：循环处理不同的增量，直到增量为0。
- for i in range(gap, n)：遍历每个组内的元素（从第gap个元素开始）。
- temp = arr[i]：保存当前元素，避免后续赋值覆盖。
- j = i - gap：计算当前元素所在组的前一个元素下标。
- while j >= 0 and arr[j] > temp：若前一个元素比temp大，后移该元素并继续向前比较；否则停止。
- arr[j + gap] = temp：找到合适位置后，将temp插入。
- gap = gap // 2：增量减半，逐步缩小分组，直到分组为1（即普通插入排序）。
举例说明（以数组[5, 3, 8, 4, 2]为例）¶
-
初始数组：
[5, 3, 8, 4, 2]，n=5，初始增量gap=5//2=2。 -
处理
gap=2：
- 分组：组1（下标0、2、4：元素5、8、2），组2（下标1、3：元素3、4）。
- 组1插入排序：i=2（元素8）：j=0（i-gap=0），arr[0]=5 <=8，无需移动。数组不变：[5,3,8,4,2]。i=4（元素2）：j=4-2=2（arr[2]=8>2），后移8到arr[4]，数组变为[5,3,2,4,8]；j=0（arr[0]=5>2），后移5到arr[2]，数组变为[5,3,5,4,8]；j=-2（找到位置），插入2到arr[0]，组1排序后：[2,3,5,4,8]。- 组2插入排序：
i=3（元素4）：j=3-2=1（arr[1]=3 <=4），无需移动。数组不变：[2,3,5,4,8]。
-
处理
gap=1（此时增量减半为1，即普通插入排序）：
-i=1（元素3）：j=0（arr[0]=2 <=3），不动。
-i=2（元素5）：j=1（arr[1]=3 <=5），不动。
-i=3（元素4）：j=2（arr[2]=5>4），后移5到arr[3]，数组变为[2,3,5,5,8]；j=1（arr[1]=3 <=4），插入4到arr[2]，数组变为[2,3,4,5,8]。
-i=4（元素8）：j=3（arr[3]=5 <=8），不动。 -
最终结果：
[2, 3, 4, 5, 8]。
总结¶
- 时间复杂度：平均约为O(n log n)，最坏情况为O(n²)，比插入排序更高效。
- 空间复杂度：O(1)，原地排序，仅需临时变量。
- 适用场景：适用于中等规模数组，尤其当元素分布不均匀时，分组排序可减少移动次数。
通过分组和逐步缩小增量，希尔排序让数组先“粗排”再“精排”，有效提升了插入排序的效率，是一种实用的排序算法。