1959 年一个叫 Donald L. Shell (March 1, 1924 – November 2, 2015) 的美国人在 Communications of the ACM 国际计算机学会月刊 发布了一个排序算法,从此名为希尔排序的算法诞生了。

注: ACM = Association for Computing Machinery,国际计算机学会,世界性的计算机从业员专业组织,创立于1947年,是世界上第一个科学性及教育性计算机学会。

希尔排序是直接插入排序的改进版本。因为直接插入排序对那些几乎已经排好序的数列来说,排序效率极高,达到了 O(n) 的线性复杂度,但是每次只能将数据移动一位。希尔排序创造性的可以将数据移动 n 位,然后将 n 一直缩小,缩到与直接插入排序一样为 1,请看下列分析。

希尔排序属于插入类排序算法。

一、算法介绍

有一个 N 个数的数列:

  1. 先取一个小于 N 的整数 d1,将位置是 d1 整数倍的数们分成一组,对这些数进行直接插入排序。
  2. 接着取一个小于 d1 的整数 d2,将位置是 d2 整数倍的数们分成一组,对这些数进行直接插入排序。
  3. 接着取一个小于 d2 的整数 d3,将位置是 d3 整数倍的数们分成一组,对这些数进行直接插入排序。
  4. 直到取到的整数 d=1,接着使用直接插入排序。

这是一种分组插入方法,最后一次迭代就相当于是直接插入排序,其他迭代相当于每次移动 n 个距离的直接插入排序,这些整数是两个数之间的距离,我们称它们为增量。

我们取数列长度的一半为增量,以后每次减半,直到增量为1。

举个简单例子,希尔排序一个 12 个元素的数列:[5 9 1 6 8 14 6 49 25 4 6 3],增量 d 的取值依次为:6,3,1

  1. x 表示不需要排序的数
  2. d = 6 [5 x x x x x 6 x x x x x] 进行直接插入排序,没有变化。
  3. d = 3 [5 x x 6 x x 6 x x 4 x x] 进行直接插入排序,排完序后:[4 x x 5 x x 6 x x 6 x x]。
  4. d = 1 [4 9 1 5 8 14 6 49 25 6 6 3] 进行直接插入排序,因为 d=1 完全就是直接插入排序了。

越有序的数列,直接插入排序的效率越高,希尔排序通过分组使用直接插入排序,因为步长比 1 大,在一开始可以很快将无序的数列变得不那么无序,比较和交换的次数也减少,直到最后使用步长为 1 的直接插入排序,数列已经是相对有序了,所以时间复杂度会稍好一点。

在最好情况下,也就是数列是有序时,希尔排序需要进行 logn 次增量的直接插入排序,因为每次直接插入排序最佳时间复杂度都为:O(n),因此希尔排序的最佳时间复杂度为:O(nlogn)

在最坏情况下,每一次迭代都是最坏的,假设增量序列为: d8 d7 d6 ... d3 d2 1,那么每一轮直接插入排序的元素数量为:n/d8 n/d7 n/d6 .... n/d3 n/d2 n,那么时间复杂度按照直接插入的最坏复杂度来计算为:

  1. 假设增量序列为 N/2 ,每次增量取值为比上一次的一半小的最大整数。
  2. O( (n/d8)^2 + (n/d7)^2 + (n/d6)^2 + ... + (n/d2)^2 + n^2)
  3. = O(1/d8^2 + 1/d7^2 + 1/d6^2 + ... + 1/d2^2 + 1) * O(n^2)
  4. = O(等比为1/2的数列和) * O(n^2)
  5. = O(等比求和公式) * O(n^2)
  6. = O( (1-(1/2)^n)/(1-1/2) ) * O(n^2)
  7. = O( (1-(1/2)^n)*2 ) * O(n^2)
  8. = O( 2-2*(1/2)^n ) * O(n^2)
  9. = O( < 2 ) * O(n^2)

所以,希尔排序最坏时间复杂度为 O(n^2)

不同的分组增量序列,有不同的时间复杂度,但是没有人能够证明哪个序列是最好的。Hibbard 增量序列:1,3,7,···,2n−1 是被证明可广泛应用的分组序列,时间复杂度为:Θ(n^1.5)

希尔排序的时间复杂度大约在这个范围:O(n^1.3)~O(n^2),具体还无法用数学来严格证明它。

希尔排序不是稳定的,因为每一轮分组,都使用了直接插入排序,但分组会跨越 n 个位置,导致两个相同的数,发现不了对方而产生了顺序变化。

二、算法实现

  1. package main
  2. import "fmt"
  3. // 增量序列折半的希尔排序
  4. func ShellSort(list []int) {
  5. // 数组长度
  6. n := len(list)
  7. // 每次减半,直到步长为 1
  8. for step := n / 2; step >= 1; step /= 2 {
  9. // 开始插入排序,每一轮的步长为 step
  10. for i := step; i < n; i += step {
  11. for j := i - step; j >= 0; j -= step {
  12. // 满足插入那么交换元素
  13. if list[j+step] < list[j] {
  14. list[j], list[j+step] = list[j+step], list[j]
  15. continue
  16. }
  17. break
  18. }
  19. }
  20. }
  21. }
  22. func main() {
  23. list := []int{5}
  24. ShellSort(list)
  25. fmt.Println(list)
  26. list1 := []int{5, 9}
  27. ShellSort(list1)
  28. fmt.Println(list1)
  29. list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
  30. ShellSort(list2)
  31. fmt.Println(list2)
  32. list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
  33. ShellSort(list3)
  34. fmt.Println(list3)
  35. }

输出:

  1. [5]
  2. [5 9]
  3. [1 3 4 5 6 6 6 8 9 14 25 49]
  4. [1 2 2 3 3 4 4 5 5 6 6 6 6 8 8 9 14 23 23 25 33 33 49 56 85 335 467 567 677]

按照之前分析的几种排序算法,一般建议待排序数组为小规模情况下使用直接插入排序,在规模中等的情况下可以使用希尔排序,但在大规模还是要使用快速排序,归并排序或堆排序。