希尔排序(Shell Sort)算法是插入排序(Insertion Sort)算法的改良版。它解决了插入排序法一次只能把元素移动一个索引距离的问题,加入间距(gap)的概念来分批并分组完成插入排序法,有效提升原本插入排序法的速度。
希尔排序法(Shell Sort)
希尔排序法的概念
希尔排序法是基于插入排序法的算法,如果您还不了解插入排序法的话,请先参考这篇文章:
希尔排序法在插入排序法的基础上添加了间距(gap)的概念,使得插入排序法可以分组运行,并且元素的移动距离可以大于一。希尔排序法会对串行由大至小,小则至 1,来选择应用在插入排序法上的间距,这样一来就可以让串行后端比较小的元素,在被使用前面几次的大间距插入排序法排序之后,就先被移动到较前端的位置,使它们在最后的插入排序法中,不需要大老远的从后端以一次一个索引距离的方式来移动到前端。
希尔排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
如果在一开始我们选择使用的间距是 3 的话,希尔排序法则会以以下的分组方式来运行插入排序法:
索引 0 1 2 3 4 5 6 7 8 9
数值 69 38 47 79
81 9 61
30 2 32
所以经过排序后,数组内的元素分布如下:
索引 0 1 2 3 4 5 6 7 8 9
数值 38 47 69 79
9 61 81
2 30 32
索引 0 1 2 3 4 5 6 7 8 9
数值 38 9 2 47 61 30 69 81 32 79
如果在下一次我们选择使用的间距是 2 的话,希尔排序法则会以以下的分组方式来运行插入排序法:
索引 0 1 2 3 4 5 6 7 8 9
数值 38 2 61 69 32
9 47 30 81 79
经过排序后,数组内的元素分布如下:
索引 0 1 2 3 4 5 6 7 8 9
数值 2 32 38 61 69
9 30 47 79 81
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 32 30 38 47 61 79 69 81
最后使用间距 1,来完成排序:
索引 0 1 2 3 4 5 6 7 8 9 数值 2 9 30 32 38 47 61 69 79 81
希尔排序法的程序实作
希尔排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n^2)}}# #{{O(n \log^2 n)}}# |
使用最差的间距。 使用 Pratt 的间距值(#{{2^p 3^q}}#)。 |
| 最佳时间复杂度 | #{{O(n \log n)}}# #{{O(n \log^2 n)}}# |
使用最佳的间距。 使用 Pratt 的间距值(#{{2^p 3^q}}#)。 |
| 平均时间复杂度 | ? #{{O(n \log^2 n)}}# |
根据间距值来决定。 使用 Pratt 的间距值(#{{2^p 3^q}}#)。 |
| 最差空间复杂度 | #{{O(1)}}# | |
| 是否稳定 | 否 | 如果是普通的插入排序法则是稳定的。 |

