【算法实践】手把手带你简单实现希尔排序

前言

希尔排序是什么？

希尔排序(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)

执行结果如下: