希尔排序

pengzhanbo

167字小于1分钟

2022-04-25

提问

希尔排序
实现

希尔排序

把数组按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至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
}