希尔排序

今天我们来介绍一个比经典的排序算法:希尔排序。该算法时以它的发明者 Donald Shell 名字命名的,改进自插入排序算法,实现简单,在中等规模的数据上性能表现不错。我们同样从算法的思路、Python 实现以及复杂度分析三个方面学习希尔排序算法。

1. 希尔排序算法思路

希尔排序又叫缩小增量排序,它是基于插入排序的改进算法,相比插入排序更加高效,但是属于不稳定算法,而插入排序则是一种稳定算法。希尔排序的基本思想是将待排序元素进行增量分组,然后在分组组内进行插入排序,随着增量的减少,每个分组组内的元素越来越多,直至增量减至1时,所有元素都分到同一个组内,执行插入排序后完成整个排序操作。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序,小的基本在前,大的基本在后。然后缩小增量,到增量为1时,其实多数情况下只需微调即可,不会涉及过多的数据移动。

2. 举例说明希尔排序算法过程

下面以 8 个数的列表为例,描述希尔排序算法的排序过程。

图片描述

3. 希尔排序复杂度分析

希尔排序的时间复杂度比较难计算,这里直接给出相关结果:

• 时间复杂度:最坏情况下,每两个数都要比较并交换一次,因此最坏情况下的时间复杂度为$O(n^2)$O(n2)最好情况下,数组是有序的,不需要交换,只需要比较,因此最好情况下的时间复杂度为 $O(n)$O(n);它的平均复杂度可以达到 $O(n^{1.3})$O(n1.3);

• 空间复杂度:由于采用数据交换的方式,并没有用到额外的空间,所以空间复杂度为 $O(1)$O(1)。

4. 希尔排序算法的 Python 实现

希尔排序的一个经典实现如下所示,接下来我们会画图描述下该代码的实现过程。

def shell_sort(nums):
 """
 希尔排序
 """
 n = len(nums)
 d = n // 2
 
 while d > 0: 
 for i in range(d, n): 
 temp = nums[i] 
 j = i 
 # 插入排序过程,可参考下图所示
 while j >= d and nums[j - d] > temp: 
 nums[j] = nums[j - d] 
 j -= d 
 nums[j] = temp
 # 每次排序数组间距减半
 d = d // 2

我们画图来对上述算法进行说明,它并没有完整依照前面的 shell 过程进行实现,不过执行过程和 shell 排序的思路是一致的。

图片描述

希尔排序的代码已经在上图中解释的非常清楚了,for 循环中每次会将该位置往前间隔 d 的列表保证有序,后面每次会在间隔 d 的列表中将 nums[i] 插入到对应的位置,并保证本次从该位置往前间隔为 d 的列表有序。每次 for 循环执行完成,间隔为 d 的列表就是有序的,即完成了希尔排序的核心过程。 接下来便是每次缩小增量 d 值,直到最后增量为0,排序结束。

5. 实例测试希尔排序代码

我们来测试希尔排序算法的性能,使用10000个随机数进行测试:

import random
import datetime
from sort_algorithms import shell_sort, insert_sort2
if __name__ == '__main__':
 nums = [random.randint(10, 10000) for i in range(10000)] 
 start = datetime.datetime.now()
 shell_sort(nums)
 # insert_sort2(nums)
 end = datetime.datetime.now()
 print('Running time: %s Seconds' % (end-start))

PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
Running time: 0:00:00.071001 Seconds

然后来看看我们用前面改进的插入排序算法 (使用前面完成的 insert_sort2() 方法) 进行测试并和希尔排序的结果对比。可以看到希尔排序的性能大概是插入排序算法的 3 倍,所以希尔排序相比插入排序算法性能提升还是非常明显的。

PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
Running time: 0:00:00.216178 Seconds

6. 小结

本节我们学习了排序中的一个经典排序算法:希尔排序,相比前面的冒泡、插入和选择排序算法在效率是有了较大提升。接下来我们要学习最后一个最常考也是面试中最常见的排序算法:快速排序算法。