希尔排序（插排改造优化）

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 变大（再由大递减），节约时间
      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());