排序算法4-希尔排序

希尔排序

• 平均时间复杂度:O(nlogn)
• 最好情况:O(nlog^2n)
• 最坏情况:O(nlog^2n)
• 空间复杂度:O(1)
• 排序方式:In-place
• 稳定性:不稳定

算法步骤:
1.先取一个小于待排序数列长度n的整数d1作为第一个增量，将所有距离为d1的倍数的记录放在同一个组中。（一般的初次取序列的一半为增量，以后每次减半，直到增量为1。）
2.在各组内进行插入排序；
3.取第二个增量d2<d1重复上述的分组和排序，直至增量为1，即所有记录放在同一组中进行插入排序。

例如待排序数组为: [1, 10, 3, 2, 5, 8, 4, 7, 9, 6]
1.第一次增量设为数组长度的一半即5, 数组被分为五组分别为[1,8]/[10,4]/[3,7]/[2,9]/[5,6]
2.然后对每组做插入排序操作，操作后的数组为[1, 4, 3, 2, 5, 8, 10, 7, 9, 6]
3.第二次增量设为之前增量的一半取整即2，数组被分为两组分别为[1,3,5,10,9]/[4,2,8,7,6]
4.然后对每组做插入排序操作，操作后的数组为[1, 2, 3, 4, 5, 6, 9, 7, 10, 8]
5.第三次增量再次设为之前增量的一半即1，数组只分为一组，排序后结束。

function shellSort(arr) {
  let len = arr.length;
  let temp,
    gap = len;
  while ((gap >>= 1)) {
    for (let i = gap; i < len; i++) {
      temp = arr[i];
      let j = i;
      for (; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

改进
希尔排序的优化主要在增量的选择，上面的实现取了2，一般都是取2或3。 至于最优值是多少貌似仍是一个数学难题。