SOURCE

// 插入排序
/**
 * 待排序分割若干子序列
 * 分别插入排序
 * 待整个序列基本有序，再全体插入排序
 * 
 * [35, 33, 42, 10, 14, 19, 27, 44]
 * 采取间隔 4
 * { 35, 14 }，{ 33, 19 }，{ 42, 27 } { 10, 44 }
 * [14, 27, 35, 42 , 19, 10, 33, 44 ]
 * 采取间隔 2
 * { 14, 27, 35, 42 }， { 19, 10, 33, 44 }
 */



function insertionSort (arr) {
  let n = arr.length;

  for (let i = Math.floor(n / 2); i > 0; i = Math.floor(i / 2)) {
    for (let j = i; j < n; j++) {
      let current = arr[j];
      // 当前分组中如果前面比后面大就换位置
      while (j >= 0 && arr[j - i] > current) {
        arr[j] = arr[j - i];
        j -= i;
      }
      // j = j-i ,相当于前一个
      arr[j] = current;
    }
  }
  return arr;
}
var arr = insertionSort([35, 33, 42, 10, 14, 19, 27, 44]);
console.log(arr);