希尔排序

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);
  }
}