javascript - 希尔排序问题

Question

请问为什么我这个写法的希尔排序不对？ (第一层gap的取值请无视)

Answer 1

发现你的大致思路对了，但是循环和步长的处理上有问题。正确的写法请参考如下：

//形参增加步数gap(实际上就相当于gap替换了原来的数字1)
function directInsertionSort(array, gap) {
  gap = (gap == undefined) ? 1 : gap;       //默认从下标为1的元素开始遍历
  var length = array.length, index, current;
  for (var i = gap; i < length; i++) {
    index = i - gap;    //待比较元素的下标
    current = array[i];    //当前元素
    while(index >= 0 && array[index] > current) { //前置条件之一:待比较元素比当前元素大
      array[index + gap] = array[index];    //将待比较元素后移gap位
      index -= gap;                           //游标前移gap位
    }
    if(index + gap != i){                   //避免同一个元素赋值给自身
      array[index + gap] = current;            //将当前元素插入预留空位
    }
  }
  return array;
}
function shellSort(array){
  var length = array.length, gap = length>>1, current, i, j;
  while(gap > 0){
    directInsertionSort(array, gap); //按指定步长进行直接插入排序
    gap = gap>>1;
  }
  return array;
}

关于希尔排序，有一篇细致入微，包含完整的分步骤讲解和gif配图。 请参考JS中可能用得到的全部的排序算法
另外，我的专栏里也有这篇文章，感兴趣可以关注我。