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 :

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

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

<3> Si l'élément (trié) est plus grand que le nouvel élément, déplacez l'élément à la position suivante ; <4> 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

<5>

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

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)

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 !