04_希尔排序

希尔排序的基本思想是把数组按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元 素越来越多，当增量减至 1 时，整个数组恰被分成一组，算法便终止。

希尔排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n^s) ，空间复杂度为 O(1) ，不是稳定排序。

点击查看代码

function shellSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return arr;

  const length = arr.length - 1;
  let gap = Math.floor(arr.length / 2);

  while (gap >= 1) {
    for (let i = gap; i <= length; i++) {
      let j = i,
        temp = arr[i];

      while (temp < arr[j - gap] && j - gap >= 0) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }

  return arr;
}