排序算法集锦系列之——希尔

[ddzy]

https://blog.yyge.top/blog/2019/04/13/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E9%9B%86%E9%94%A6%E7%B3%BB%E5%88%97%E4%B9%8B%E2%80%94%E2%80%94%E5%B8%8C%E5%B0%94/

个人博客 - 多做, 多思考, 多记录

[ddzy]

要点: 动态增量 + 插入排序

[ddzy]

个人认为比较容易理解的一种算法:

function shellSort(originArr) {
  let gap = originArr.length;

  while ((gap = ~~(gap / 2))) {
    for(let i = 0; i < originArr.length; i++) {
      // j -= gap, 实际上只是为了让循环执行一次, 也就是只比对 gap 差距的两个数
      for(let j = i + gap; j >= 0; j -= gap) {
        if (originArr[j] < originArr[j - 1]) {
          const temp = originArr[j];
          originArr[j] = originArr[j - 1];
          originArr[j - 1] = temp;
        }
      }
    }
  }

  return originArr;
}