思想

插入排序的升级版

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

image-20200324202401975.png

img

实现

/*
  冒泡排序:
  平均时间复杂度:O(nlogn), 最差时间复杂度:O(ns 1<s<2), 是不稳定排序, 需要额外空间O(1) 
 */
function shell(array) {//交换法, 效率不高
  let temp = 0
  for (let gap = Math.floor(array.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < array.length; i++) {
      for (let j = i - gap; j >= 0; j -= gap) {
        if (array[j] > array[j + gap]) {
          temp = array[j]
          array[j] = array[j + gap]
          array[j + gap] = temp
        }
      }
    }
  }
}
function shell2(array) {//移动法, 效率高, 第一种逻辑
  for (let gap = Math.floor(array.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < array.length; i++) {
      let curIndex = i 
      let insertValue = array[curIndex]
      while (curIndex - gap >= 0 && insertValue < array[curIndex - gap]) {
        array[curIndex] = array[curIndex - gap]
        curIndex -= gap
      }
      array[curIndex] = insertValue
    }
  }
}
function shell3(array) {//移动法, 效率高, 第二种逻辑 
  for (let gap = Math.floor(array.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < array.length; i++) {
      let compareIndex = i - gap
      let insertValue = array[i]
      while (compareIndex >= 0 && insertValue < array[compareIndex]) {
        array[compareIndex + gap] = array[compareIndex]
        compareIndex -= gap
      }
      array[compareIndex + gap] = insertValue
    }
  }
}
let array = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
shell3(array)
console.log(array);