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中可能用得到的全部的排序演算法
另外，我的專欄裡也有這篇文章，有興趣可以追蹤我。