希爾排序
1959年Shell發(fā)明，第一個(gè)突破O(n2)的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版斩熊。它與插入排序的不同之處在于蕴忆，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。
希爾排序原理圖解：
希爾排序圖解
接下來直接上代碼：
function sort(list) {
let len = list.length;
// 初始增量為數(shù)組的一半
let gap = Math.floor(len / 2);
while(gap > 0) {
// 內(nèi)部使用插入排序
for(let i = gap; i < len; i++) {
let m = list[i];
let j = i;
while(j - gap >= 0) {
let n = list[j - gap];
if (m < n) {
list[j - gap] = m;
list[j] = n;
}
j -= gap;
}
}
gap = Math.floor(gap / 2);
}
}
