希尔排序
1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序原理图解:
接下来直接上代码:
function sort(list) {
let len = list.length;
// 初始增量为数组的一半
let gap = Math.floor(len / 2);
while(gap > 0) {
// 内部使用插入排序
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);
}
}