7. 希尔排序

算法描述

希尔排序是插入排序的一种改进。首先我们回忆一下插入排序的性质：

• 在大多数元素已经有序的情况下，插入排序的工作量较小
• 在元素数量较少的情况下，插入排序的工作量较小

针对这两个性质进行优化，对原始数组进行处理。
对元素进行分组，然后进行组内排序，粗调。

上面示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，增量的选择可以有很多种，我们在示例中所用的逐步折半的增量方法，是 Donald Shell 在发明希尔排序时提出的一种朴素方法，被称为希尔增量。

希尔排序利用分组粗调的方式减少了直接插入排序的工作量，使得算法的平均复杂度低于 o(n^2)。
但是在某些极端情况下，可能比插入排序更慢。比如：

上面的数组无论是以4为增量，还是以2为增量，每组内部的元素都没有任何交换。一直到我们把增量缩减为1，数组才会按照直接插入排序的方式进行调整。
对于这样的数组，希尔排序不但没有减少直接插入排序的工作量，反而白白增加了分组操作的成本。

动图演示

算法实现

这里用到了 >> 操作符，表示向右移一位。相当于除以 2 的 x 次方，并且向下取整。
插入排序是往前一位比较，如果比当前元素大，则往后移动一位。这里是往后移动 gap 位。

/**
 * 希尔排序
 * @param {number[]} arr 数组
 */
const shellSort = (arr) => {
  for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
    for (let i = gap; i < arr.length; i++) {
      const temp = arr[i]
      let j
      for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
  return arr
}