function insertionSort4Gap(arr, gap) {
var len = arr.length;
gap = typeof gap === 'number' && gap > 0 ? gap : 1;
// for(let i = gap; i < len; i += gap) {
for(let i = gap; i < len; i++) {
var cur = arr[i];
var j = i - gap;
while(j >= 0 && arr[j] > cur) { // 這一步岗仑，由于 gap 變大（再由大遞減）痘番，節(jié)約時(shí)間
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = cur;
}
return arr;
}
function shellSort(arr) {
var len = arr.length;
var gap = 1;
while(gap < len / 3) {
gap = gap * 3 + 1;
}
for(gap; gap > 0; gap = Math.floor(gap / 3)) {
insertionSort4Gap(arr, gap);
}
return arr;
}
console.log(new Date().getTime());
shellSort(arr);
console.log(new Date().getTime());
console.log(arr);
Sorting_shellsort_anim.gif
var arr = [4321, 34, 5643, 4321, 654, 2, 4389, 34, 564, 389, 3, 10, 23, 34, 89, 10, 2, 543, 4813, 89324, 765, 3, 2, 2, 4321, 34, 5643, 4321, 654, 2, 4389, 34, 564, 389, 3, 10, 23, 34, 89, 10, 2, 543, 4813, 89324, 765, 3, 2, 2, 4321, 34, 5643, 4321, 654, 2, 4389, 34, 564, 389, 3, 10, 23, 34, 89, 10, 2, 543, 4813, 89324, 765, 3, 2, 2];
console.log(new Date().getTime());
insertionSort(arr);
console.log(new Date().getTime());
