此页内容

约 167 字小于 1 分钟

2022-04-25

提问

  1. 希尔排序
  2. 实现

希尔排序

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

实现

function hillSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return arr;
  const len = arr.length;
  if (!Array.isArray(arr) || len <= 1) return;
  for (let gap = parseInt(len >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
    for (let i = gap; i < len; i++) {
      let temp = arr[i];
      let j = i;

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