算法-排序算法：希尔排序（Shell Sort）【O(n^2)】

本文主要是介绍算法-排序算法：希尔排序（Shell Sort）【O(n^2)】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

希尔排序（Shell Sort）：1959年Shell发明，第一个突破O(n2)的排序算法，是插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

一、希尔排序-算法描述：

先将整个待排序的序列A按照一个“增量”(gap)分割成为若干子序列，然后分别进行直接插入排序，具体算法描述：

选择一个增量序列(gap 序列) ${t_1, t_2, …, t_i, t_j, …,1}$ ，其中t_i>t_j，此增量序列元素总数为n；
按增量序列(gap序列)元素总数n，对序列进行n趟“直接插入排序”；
每趟排序，根据对应的增量(gap=t_i)，将待排序列分割成若干长度为m 的子序列，分别对子序列进行直接插入排序。仅增量因子为1(gap=1) 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

二、希尔排序-过程分析

在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这一系列增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。
希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

三、希尔排序-动图演示

在这里插入图片描述

四、希尔排序-代码实现

def shell_sort(alist):n = len(alist)# 初始步长gap = n // 2while gap > 0:# 插入排序，与普通的插入排序的区别就是gap步长替代1for i in range(gap, n):j = i# 插入排序while j >= gap and alist[j - gap] > alist[j]:alist[j - gap], alist[j] = alist[j], alist[j - gap]j -= gap# 缩短gap步长，得到新的步长gap = gap // 2alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shell_sort(alist)
print(alist)