Explication détaillée de l'algorithme de tri par tas Javascript

Cet article présente principalement l'algorithme de tri du tas Javascript et ses exemples. C'est très pratique. Les amis dans le besoin peuvent s'y référer.

Le tri des tas est divisé en deux processus :

1. Créer un tas.

Un tas est essentiellement un arbre binaire complet, qui doit satisfaire : le mot-clé de tout nœud non-feuille dans l'arbre n'est pas supérieur (ou pas inférieur) au mot-clé de ses nœuds enfants gauche et droit ( s'ils existent).

Le tas est divisé en : grand tas de racines et petit tas de racines. Le grand tas de racines est utilisé pour le tri ascendant, et le petit tas de racines est utilisé pour le tri décroissant.

S'il s'agit d'un grand tas racine, ajustez le nœud avec la plus grande valeur à la racine du tas via la fonction d'ajustement.

2. Enregistrez la racine du tas à la queue et appelez la fonction d'ajustement sur les séquences restantes, une fois l'ajustement terminé, enregistrez le tas maximum à la queue -1 (-1, -2,... , -i) , puis ajustez les séquences restantes et répétez ce processus jusqu'à ce que le tri soit terminé.

//调整函数
function headAdjust(elements, pos, len){
  //将当前节点值进行保存
  var swap = elements[pos];
  //定位到当前节点的左边的子节点
  var child = pos * 2 + 1;
  //递归，直至没有子节点为止
  while(child < len){
    //如果当前节点有右边的子节点，并且右子节点较大的场合，采用右子节点
    //和当前节点进行比较
    if(child + 1 < len && elements[child] < elements[child + 1]){
      child += 1;
    }
    //比较当前节点和最大的子节点，小于则进行值交换，交换后将当前节点定位
    //于子节点上
    if(elements[pos] < elements[child]){
      elements[pos] = elements[child];
      pos = child;
      child = pos * 2 + 1;
    }
    else{
      break;
    }
    elements[pos] = swap;
  }
}
//构建堆
function buildHeap(elements){
  //从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
  //将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
  //直至构建出大顶堆（升序为大顶，降序为小顶）
  for(var i=elements.length/2; i>=0; i--){
    headAdjust(elements, i, elements.length);
  }
}
function sort(elements){
  //构建堆
  buildHeap(elements);
  //从数列的尾部开始进行调整
  for(var i=elements.length-1; i>0; i--){
    //堆顶永远是最大元素，故，将堆顶和尾部元素交换，将
    //最大元素保存于尾部，并且不参与后面的调整
    var swap = elements[i];
    elements[i] = elements[0];
    elements[0] = swap;
    //进行调整，将最大）元素调整至堆顶
    headAdjust(elements, 0, i);
  }
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log(&#39;before: &#39; + elements);
sort(elements);
console.log(&#39; after: &#39; + elements);

Efficacité :

Complexité temporelle : Meilleure : O(nlog2n), Pire : O(nlog2n), Moyenne : O(nlog2n).

Complexité spatiale : O(1).

Stabilité : Instable

Ce qui précède représente l'intégralité du contenu de ce chapitre. Pour plus de didacticiels connexes, veuillez visiter le Tutoriel vidéo JavaScript !