Python 实现经典算法之希尔排序

简介

希尔排序(Shell Sort)是插入排序（Python 实现经典算法之插入排序）的一种，它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

原理

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

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对富贵论坛全体记录进行依次直接插入排序。

复杂度

希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。

希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。

步骤n 为数组长度，首先取一个整数 d1=n/2，将元素分为 d1 个组，每组相邻量元素之间距离为 d1-1，在各组内进行直接插入排序；取第二个整数 d2=d1/2，重复步骤 1分组排序过程，直到 di=1，即所有元素在同一组内进行直接插入排序。动图演示

实例代码

###

# author: 今日头条：技术好奇心

###

# 希尔排序例子

def shell_sort(arr):

# 第一次分组（结果向下取整）

d = len(arr) // 2

# 将 d 看做隔 d 个距离摸一张牌，而不是依次按照顺序摸牌

while d >= 1:

# 将 i 看做摸到的牌的下标

for i in range(d, len(arr)):

# 将摸到的牌储存到 tmp

tmp = arr[i]

# 将 j 看做手里的牌的下标

# （注意这里和插入排序的区别，是d，表示间隔，而不是直接取前一位）

j = i - d

# 如果手里的牌大于摸到的牌（这里的小循环和上一篇文章插入排序基本一致）

while j >= 0 and arr[j] > tmp:

# 将手里的牌往右移一个位置（将手里的牌赋值给下一个位置）

arr[j + d] = arr[j]

# 将手里的牌的下标减 d，再次准备与摸到的牌进行比较

j -= d

# 将摸到的牌插入到 j+d 位置

arr[j + d] = tmp

# 每一轮排序后打印一次看看排序结果

print(arr)

# 结束后，再次分割，去处理另一部分

d //= 2

# 执行

if name == ‘main’:

# 建立演示数组

arr = [5, 7, 4, 6, 3, 1, 2, 9, 8]

# 执行排序方法

shell_sort(arr)

# 看看比较完之后数组的样子

print(’-------------------- 技术好奇心 -------------------’)

print(arr)

运行结果：

[3, 1, 2, 6, 5, 7, 4, 9, 8]

[2, 1, 3, 6, 4, 7, 5, 9, 8]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

-------------------- 技术好奇心 -------------------

[1, 2, 3, 4, 5, 6, 7, 8, 9]