希尔排序

希尔排序是希尔于1959年提出的一种排序算法，是插入排序的改进版本，也称为缩小增量排序，同时他是第一批冲破O（n^2)的排序算法之一。当时出现过许多排序算法，可是都没能突破O(n^2)，但是希尔排序的出现改变了一切。

思路

该算法的基本思想是，将元素用增量来切割成多个子数组，并不是真正的切割，而是用增量来表示，如果有一个数组为:
[3, 4, 3, 2, 5, 7, 3, 5]，我们设刚开始的增量是length/2也就是4，这个时候arr[0]的下一个元素就是arr[4],arr[1]的下一个元素是arr[5]，arr[2]->arr[6],arr[3]->arr[7],被分成了4组，这个时候我们只需对每一组进行插入排序，排序完成之后数组会变得相对有序，这个时候我们缩小增量为2,这个时候arr[0]->arr[2]->arr[4]->arr[6]为一组，arr[1]->arr[3]->arr[5]->arr[7]为一组，这个时候再对这两组分别进行插入排序，插入排序有个特点就是对相对有序的数组排序非常快，直到增量变成了1，我们再进行一次插入排序，就使得整个数组有序。

代码

/**
 *
 * @param {number[]} arr
 */
export function shellSort(arr) {
  const n = arr.length;
  // 创建希尔序列,以克努特序列为例
  let gap = 1;
  while (gap < n / 3) {
    gap = gap * 3 + 1; // 1, 4, 13, 40 ...... (3^k - 1) / 2
  }

  while (gap >= 1) {
    // 正常插入排序
    for (let i = 0; i < gap; i++) {
      for (let j = i + gap; j < n; j += gap) {
        const temp = arr[j];
        while (j > 0 && arr[j - gap] > temp) {
          arr[j] = arr[j - gap];
          j -= gap;
        }
        arr[j] = temp;
      }
    }
    gap = Math.floor(gap / 3);
  }
}

看上去是不是和插入排序一摸一样，只是往后面找的下一个待插入的元素为arr[j+gap]，这里我们使用了克努特序列，其实你自己制定一个序列也是可以的，只是这些序列被证明过是稳定且复杂度较低的序列，希尔排序在使用不同的序列时间复杂度是不同的，所以希尔排序是一种不稳定的排序。下面我们再写一个希尔序列的例子，也就是每次对长度除以2 。

/**
 * @description 使用希尔序列排序
 * @param {number[]} arr
 */
export function shellSort2(arr) {
  const n = arr.length;
  let gap = Math.floor(n / 2);
  while (gap >= 1) {
    for (let i = 0; i < gap; i++) {
      for (let j = i + gap; j < n; j += gap) {
        const temp = arr[j];
        while (j > 0 && arr[j - gap] > temp) { // 插入过程
          arr[j] = arr[j - gap];
          j -= gap;
        }
        arr[j] = temp;
      }
    }
    gap = Math.floor(gap / 2);
  }
}

这段代码是我直接复制上面的，只改了gap，是不是感觉很简单，重点还是在插入排序，只要插入排序懂了希尔排序就是信手拈来，下面给出几种常用的序列。

常用增量序列

• 希尔（shell）序列：Ｎ / 2， N / 4，......, 1（重复除2）N为数组的长度。
• 希伯德（Hibbard）序列：1，3，7，...., 2^k - 1 。
• 马努特（Knuth）序列：1，4，13，... ，(3^k-1)/2 。
• 赛奇威克（Sedgewick）序列：1，5，19，41，109，...

总结

上面我们演示了希尔序列和马特努序列的希尔排序，其他序列我就不一一演示了，不同的序列对不同的数据规模时间复杂度是不同的，是不是感觉很有意思，希尔排序说到底还是插入排序，只要插入排序懂了，希尔排序是很好理解的。