思想
插入排序的升级版
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至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);
