排序：希尔排序

原理

希尔排序是插入排序的升级版。当我们谈论希尔排序时我们先谈下插入排序。
已知插入排序是从数组左端开始遍历，将使得遍历过的元素保持有序。
考虑两种情况：

• 数组是部分有序的
• 数组并不是部分有序，且小的元素普遍分布在右端

前一种情况当然对于插入排序是有利的，在遍历数组的过程中，只须进行少数几次比较与交换即可实现排序。
而第二种情况，意味着要经过多次交换，才能将这些分布在右端的小元素移动到左端，费时费力。

希尔排序优化了快速排序，主要步骤如下：

1. 使得数组中相隔 h 的元素都是有序的；然后减小 h 的值，使得这个时候数组中相隔 h 的元素也是有序的。
2. 使用一次插入排序，完成排序。

其中，第一步是将间隔为 h 的元素进行插入排序，即抽出数组中间隔 h 的元素，将它们排序。
这样一来，整个数组即为部分有序的，有利于第二部的插入排序。

例子

假如给定一个乱序数组：

[10, 9, 11, 18, 5, 1]

利用希尔排序进行排序：

其中当 h 为 4 时，将数组中每相隔四个元素抽出，将这些元素进行插入排序。以此来实现整个数组的部分有序。接下来，减小 h 的值，这里直接减为 1, 此时对数组进行的插入排序，即为一般的插入排序。

代码

/**
 * 指定数组，交换数组中两个元素的位置
 * @param {Array} list 数组
 * @param {Number} i 元素 1 的索引
 * @param {Number} j 元素 2 的索引
 */
const swap = (list, i, j) => {
  let temp = list[i]
  list[i] = list[j]
  list[j] = temp
}

// 希尔排序
const shellSort = (list) => {

  let len = list.length
  let h = 1

  while (h < len / 3) {
    h = 3 * h + 1
  }

  while (h >= 1) {
    for (let i = h; i < len; i++) {
      for (let j = i; j >= h && list[j] < list[j - h]; j -= h) {
        swap(list, j, j - h)
      }
    }

    h = parseInt(h / 3)
  }

  return list

}

代码中出现了一个特殊的常数因子 3, 当然你也可以指定其他你认为合适的数字。