JavaScript implémente le tri par insertion de l'algorithme de tri classique

Bien que l'implémentation du code du tri par insertion ne soit pas aussi simple et grossière que le tri à bulles et le tri par sélection, son principe devrait être le plus simple à comprendre, car quiconque a joué au poker devrait être capable de le comprendre en quelques secondes. Comme pour trier une main de poker, nous commençons avec notre main gauche vide et les cartes sur la table tournées vers le bas. Nous prenons ensuite à chaque fois une carte de la table et l’insérons dans la bonne position dans la main gauche. Pour trouver la position correcte d'une carte, nous la comparons avec toutes les cartes déjà dans la main de droite à gauche. Les cartes détenues dans la main gauche sont toujours triées et étaient à l'origine les premières cartes de la pile sur la table.

1) Principe de l'algorithme

La description de l'algorithme de tri par insertion (Insertion-Sort) est un algorithme de tri simple et intuitif. Il fonctionne en construisant une séquence ordonnée. Pour les données non triées, il analyse d'arrière en avant dans la séquence triée pour trouver la position correspondante et l'insérer. Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui n'utilise que l'espace supplémentaire O(1). Par conséquent, pendant le processus de numérisation d'arrière en avant, il est nécessaire de décaler de manière répétée et progressive le tri par insertion. éléments triés vers l'arrière, fournissant un espace d'insertion pour le dernier élément.

2) Description et implémentation de l'algorithme

De manière générale, le tri par insertion est implémenté sur les tableaux en utilisant in-place. L'algorithme spécifique est décrit comme suit :

f35d6e602fd7d0f0edfa6f7d103c1b57 À partir du premier élément, l'élément peut être considéré comme trié

2cc198a1d5eb0d3eb508d858c9f5cbdb après l'élément trié Scannez d'arrière en avant dans la séquence ;

5bdf4c78156c7953567bb5a0aef2fc53 Si l'élément (trié) est plus grand que le nouvel élément, déplacez l'élément à la position suivante ; 23889872c2e8594e0f446a471a78ec4c Répétez les étapes 3. Jusqu'à ce que vous trouviez une position où l'élément trié est inférieur ou égal au nouvel élément

43ad812d3a971134e40facaca816c822

efbfa0de8737dc86eae413541a49df20 Répétez les étapes 2 à 5.

3) Implémentation du code JavaScript

Tri par insertion amélioré : utilisez la recherche binaire pour trouver la position d'insertion.

function insertSort(arr) { 
    for (var i = 1; i < arr.length; i++) { 
      var temp = arr[i]; 
      var j = i - 1; 
      while (j >= 0 && arr[j] > temp) { 
        arr[j + 1] = arr[j]; 
         j--; 
      } 
      arr[j + 1] = temp; 
    } 
    return arr; 
 } 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(insertSort(arr));

Étapes :
                                                              La recherche binaire trouve la position du premier nombre de la séquence qui est plus grand que lui

   ;                                           avec le nouvel élément étant inséré dans cette position ;                                 >

Meilleur cas : le tableau d’entrée est trié par ordre croissant. T(n) = O(n)
Dans le pire des cas : le tableau d'entrée est trié par ordre décroissant. T(n) = O(n2)
Situation moyenne : T(n) = O(n2)

Ce qui précède constitue l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. J'espère également que tout le monde en apprendra davantage. Supportez le site Web chinois PHP.

function binaryInsertionSort(arr) { 
   for (var i = 1; i < arr.length; i++) { 
     var key = arr[i],left = 0,right = i - 1; 
     while (left <= right) { 
        var middle = parseInt((left + right) / 2); 
        if (key < arr[middle]) { 
          right = middle - 1; 
        } else { 
          left = middle + 1; 
        } 
     } 
     for (var j = i - 1; j >= left; j--) { 
        arr[j + 1] = arr[j]; 
     } 
     arr[left] = key; 
    } 
    return arr; 
} 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(binaryInsertionSort(arr));

Pour plus d'articles liés au tri par insertion utilisant JavaScript pour implémenter l'algorithme de tri classique, veuillez faire attention au site Web PHP chinois !