希尔排序

希尔排序

希尔排序（Shell Sort）也称 递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时，再对全体记录进行依次直接插入排序。

算法原理

先将整个待排元素序列分割成若干个子序列（由相隔某个 增量 的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

1. 先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组
2. 所有距离为 d1 的背书的记录放在同一个组中，在各组内进行直接插入排序
3. 取第二个增量 d2 小于 d1 重复上述的分组和排序，直至所取的增量 dt = 1

算法分析

• 平均时间复杂度：O(nlog2n)
• 最佳时间复杂度：
• 最差时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定
• 复杂性：较复杂

希尔排序的效率取决于增量值 gap 的选取，时间复杂度并不是一个定值。

开始时，gap 取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap 值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。

最优的空间复杂度为开始元素已排序，则空间复杂度为 0；最差的空间复杂度为开始元素为逆排序，则空间复杂度为 O(n)；平均的空间复杂度为 O(1) 希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化。比如上面的例子中希尔排序中相等数据 5 就交换了位置，所以希尔排序是不稳定的算法。

算法实现

const shellSort = function (arr) {
  let len = arr.length,
    temp,
    gap = 1

  // 动态定义间隔序列
  while (gap < len / 5) {
    gap = gap * 5 + 1
  }

  for (gap; gap > 0; gap = Math.floor(gap / 5)) {
    for (let i = gap; i < len; i++) {
      temp = arr[i]
      let j = i - gap

      for (; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }

      arr[j + gap] = temp
    }
  }

  return arr
}

参考资料

• 五分钟学会一个高难度算法：希尔排序