希尔排序

希尔排序的思路是消除数组中的逆序对，是在插入排序算法上的改良，其根据一定的规则选取增量序列 D(k)·D(k-1)·D(k-2)···1，增量序列的最后一项必须是 1,分别以对 D(k)至 1 为间距对数组进行插入排序(因为采取了对 D(k-1)为间距的插入排序之后并不会使得 D(k)为间距进行插入排序之后的结果变坏这是希尔排序的理论基础)，此刻数组会变得大致有序，最后再进行一次（间距 D 为 1）插入排序，从而使得数组有序。

用通俗易懂的语言描述就是，举个例子，我先对数组使用一次 4 （D(k)）为间距的插入排序，得到一个结果，在这个结果上以 2(即 D(k-1), 这个间距完成之后，并不会让之前 4 为间距的插入排序的结果变坏) 为间距再进行一次插入排序，又的到一个结果，最后，我对数组使用一次纯粹(因为间隔是 1，所以说它纯粹)的插入排序。

排序过程

算法实现

/**
 * 对数组进行希尔排序
 * @param {Array<number>} arr 需要进行排序的数组
 */
function shellSort(arr) {
  // 选取 N/2->N/4->N/8->···->1的增量序列
  for (let D = Math.floor(arr.length / 2); D >= 1; D = Math.floor(D / 2)) {
    // 以间距D对数组进行插入排序
    for (let i = D; i < arr.length; i++) {
      let cur = arr[i];
      let j = i;
      // 注意这儿需要取到等于
      while (j >= D && arr[j - D] > cur) {
        arr[j] = arr[j - D];
        j -= D;
      }
      arr[j] = cur;
    }
  }
}

复杂度与稳定性

希尔排序的时间复杂度是O(n*logn)，是不稳定的排序算法。

希尔排序的算法复杂度的分析是个世纪难题，其算法的时间复杂度跟你选择的增量序列有关系，有兴趣的朋友可以自行了解这部分的内容。