希尔排序 - wangshengliang

希尔排序仍然是插入排序的一种改进版本。

希尔排序主要利用到了插入排序的两个特点：

如果序列基本有序，那么时间复杂度能够达到 O(n) 级别
如果数据量比较小，即便是最坏情况 O(n²) 也和 O(n) 拉不开差距，此时效率也比较高

核心思想#

希尔排序的核心思想是采用分组的策略来对数据进行排序。

这里可以通过一个叫增量的东西，增量的选择方式比较多，这里介绍一种常见的选择方式，那就是取序列长度的一半。

例如下面的序列：

36  27  20  60  55  7   28   36   67   44   16

在这个序列中，存在 11 个数，增量 d 就为 11 / 2 = 5。

增量实际上就是一个一个间隔值，表示间隔多少个数取下一个数字。

例如：一开始下标是 0 ---> 36

下标+增量 = 5 ---> 7

根据增量，就可以对元素进行一个分组操作。

算法追踪#

第一组

下标从 0 开始。间隔是 5，对应的下标 [0, 5, 10]，这三个下标对应的元素 [36, 7, 16]，那么这三个数字就是一组。

接下来就对这三个数进行插入排序

第二组

下标从 1 开始。间隔是5，对应的下标就是[1, 6]，对应的元素[27, 28]

第三组

下标从 2 开始，间隔是5，取到的下标就有[2, 7]，对应的值就为[20， 36]

第四组

下标从 3 开始，间隔是 5，取到的下标有[3, 8]，对应的元素有[60, 67]

第五组

下标从 4 开始，间隔是 5，取到的下标[4, 9]，对应的元素就是 [55, 44]

同样对这两个数进行插入排序：

目前为止，增量 5 的所有分组就全部排好序了。

注意：增量为多少，就会分多少个组。

接下来需要更新增量。接下来增量就会变成上一轮增量的一半。增量 = 5 / 2 = 2 也就是说，这一次会分为两个组。

第一组

下标从 0 开始，这一组的下标就是[0, 2, 4, 6, 8, 10]，对应的元素就是[7, 20, 44, 28, 67, 36]

接下来还是针对这一组做插入排序，排序后的结果如下：

第二组

下标从 1 开始，对应的下标就是 [1, 3, 5, 7, 9]，这些下标对应的元素[27, 60, 16, 36, 55]

仍然对这一组做插入排序

至此，第二轮希尔排序也就结束了。总共是两个组。第二轮排序下来后相比第一轮又要有序一些了。

继续更新增量 = 2 / 2 = 1 其实就是一个组，对序列里面所有的数进行插入排序。目前序列已经基本有序，涉及到的交换非常的少：

这一轮只有 44 和 55 进行交换，然后整个排序结束。

总结：

一开始增量比较大，意味着分组多，但是每一组的元素比较少，所以效率比较高。
后面增量会越来越小，意味着分组减少，每一组的元素会增多，但是随着增量的减少，每一组组内的元素也越来越有序。所以效率也很高。

另外说一下增量 [5, 2, 1]，每次取一半。增量是不断在减少的，因此希尔排序又被称之为 缩小增量排序。

关于增量的选择有很多其他的方式，不同的方式，效率不同。但是不管哪一种方式，最后一轮增量一定为 1.

代码实现#

function shellSort(arr) {
  let n = arr.length // 数组的长度
  let gap = Math.floor(n / 2) // gap就是增量

  // 外面的循环表示的是增量的轮数，增量有几个数，这里就会循环多少次
  while (gap > 0) {
    // 根据当前的增量值，对每一组进行一个插入排序
    // 这个 for 循环就是在处理同一组的元素
    for (let i = gap; i < n; i++) {
      let temp = arr[i] // 暂存当前的元素
      let j = i // 将 j 设置为当前索引 i，主要是用来寻找插入位置

      // 将当前元素按照间隔进行插入排序
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap]
        j -= gap
      }

      arr[j] = temp // 将暂存的元素放入到正确的位置
    }

    // 更新 gap 值
    gap = Math.floor(gap / 2)
  }
}

const arr = [36, 27, 20, 60, 55, 7, 28, 36, 67, 44, 16]
shellSort(arr)
console.log(arr)

外层第一个 while 循环：负责循环增量
内层的 while 循环：查看每一个分组间隔的元素是否正确，不正确的话就将当前元素与间隔内前一个元素进行交换。
中间的 for 循环：这个循环实际上是在处理同组的元素。

数组为：[36, 27, 20, 60, 55, 7, 28, 36, 67, 44, 16]
下标为：[ 0,  1,  2,  3,  4, 5,  6,  7,  8,  9, 10]
gap = 5;
for循环第一轮
i: 5
取到的元素：7、36（第一组）
i: 6
取到的元素：28、27（第二组）
i: 7
取到的元素：36、20（第三组）
i: 8
取到的元素就是 67、60（第四组）
i: 9
取到的元素就是 44、55（第五组）
i: 10
取到的元素就是 16、7、36（第一组）

复杂度#

时间复杂度：O(nlogn)
空间复杂度：O(1)

稳定性#

希尔排序是一种 不稳定 的排序。

-EOF-