javascript - Problème de tri des collines

Question

Excusez-moi, pourquoi Hill trie-t-il mal mes écrits ? (Veuillez ignorer la valeur de l'écart de la première couche)

Answer 1

J'ai trouvé que votre idée générale est correcte, mais il y a un problème avec le traitement des boucles et des tailles de pas. Veuillez vous référer à ce qui suit pour connaître la méthode d'écriture correcte :

//形参增加步数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;
}

À propos du tri Hill, il existe un article détaillé qui comprend des explications complètes étape par étape et des gifs. Merci de vous référer à tous les algorithmes de tri pouvant être utilisés en JS
De plus, j'ai également cet article dans ma chronique, si vous êtes intéressé, vous pouvez me suivre.