介绍

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

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

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

复杂度

• 平均时间复杂度：根据步长序列的不同而不同。
• 最坏时间复杂度：根据步长序列的不同而不同。已知最好的：$O(n\log^2 n)$。
• 最优时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

动画

实现

JavaScript

/*
 * Shell Sort sorts an array based on  insertion sort algorithm
 * more information: https://en.wikipedia.org/wiki/Shellsort
 */
export function shellSort (items) {
  let interval = 1

  while (interval < items.length / 3) {
    interval = interval * 3 + 1
  }

  while (interval > 0) {
    for (let outer = interval; outer < items.length; outer++) {
      const value = items[outer]
      let inner = outer

      while (inner > interval - 1 && items[inner - interval] >= value) {
        items[inner] = items[inner - interval]
        inner = inner - interval
      }
      items[inner] = value
    }
    interval = (interval - 1) / 3
  }
  return items
}

参考

• 希尔排序 - 维基百科，自由的百科全书 (opens new window)