前言

希尔排序是什么？

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进版本。该方法又称缩小增量排序或者递减增量排序算法，跟插入排序不一样的是希尔排序是非稳定排序算法。因 D.L.Shell 于 1959 年提出而得名。

希尔排序算法实质上是一种分组插入方法。他的基本思想如下:

设待排序元素序列有 n 个元素,选择一个增量序列 d1，d2，……，dt，其中 di > dj, dt = 1；先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序(之前写过一篇关于插入排序的文章,这里就不再赘述,需要的童鞋可点击连接了解《【算法实践】手把手带你快速实现插入排序》)；然后，取第二个增量 d2<d1 重复上述的分组和排序，直至所取的增量 dt=1(dt<dt-1<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

注：由于开始时，dt 的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期 dt 取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

下图是插入排序和希尔排序的对比:

希尔排序的平均时间复杂度:O(nlogn) 最好情况和最坏情况都是 O(n⋅logn2),空间复杂度是 O(1),是一种不稳定排序.

图解希尔排序

增量序列 d1，d2，……，dt，其中 di > dj, dt = 1

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 dt，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

如现有以下 n(6)个数:排序前: [22, 23, 48, 23, 18, 7]

希尔排序中增量的取法:

增量 dt 的取法有各种方案。最初 shell 提出取 dt=n/2 向下取整，dt=dt/2 向下取整，直到 dt=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来 Knuth 提出取 dt=n/3 向下取整+1.还有人提出都取奇数为好，也有人提出 dt 互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异

增量 dt 的取值方法是：(n/3 的值向下取整 )+ 1

1. 第一趟排序 dt 的取值为(6/3 的值向下取整 )+ 1=3,即对比的数据间隔为 3,分成 3 组

2. 第二趟排序 dt 的取值为(3/3 的值向下取整 )+ 1=2,即对比的数据间隔为 2,一共分成 2 组

3. 第三趟排序 dt 的取值为(2/3 的值向下取整 )+ 1=1,即对比的数据间隔为 1,两两比较只剩下一个分组

直到 dt=1 时，就是对整个数列做最后一次调整，因为前面的序列调整已经使得整个序列部分有序，所以最后一次调整也变得非常快

从上面的图示中可以看到粉红色方块的 23 本来在紫色方块的 23 前面,排序完成后,粉红色方块的 23 排序到紫色方块的 23 后面,可看出希尔排序是个不稳定的排序算法.

代码实现

导入 math 库,math 库是 Python 内置的标准库,里面定义了与数学相关的函数

import math

定义排序函数 shellSort():

def shellSort(arr):    gap=1    while(gap < len(arr)/3):        gap = gap*3+1    while gap > 0:        for i in range(gap,len(arr)):            temp = arr[i]            j = i-gap            while j >=0 and arr[j] > temp:                arr[j+gap]=arr[j]                j-=gap            arr[j+gap] = temp        gap = math.floor(gap/3)    return arr

验证算法:

arrList = [22,23,48,23,18,7]print('排序前:',arrList)
sortedArr = shellSort(arrList)
print('排序后:',sortedArr)

执行结果如下: