Explication détaillée du tri par insertion dans la série d'algorithmes de tri PHP

Cet article présente principalement en détail les informations pertinentes sur le tri par insertion dans la série d'algorithmes de tri PHP. Il a une certaine valeur de référence. Les amis intéressés peuvent se référer à

Tri par insertion<.>

Il existe une séquence de données déjà ordonnée. Il est nécessaire d'insérer un numéro dans cette séquence de données déjà organisée, mais il est nécessaire que la séquence de données soit toujours ordonnée après l'insertion. Dans ce cas, un numéro est utilisé Nouveau. méthode de tri - méthode de tri par insertion. L'opération de base du tri par insertion consiste à insérer une donnée dans les données ordonnées déjà triées, obtenant ainsi une nouvelle donnée ordonnée avec le nombre plus un. L'algorithme convient à une petite quantité de données. la complexité du tri des données est O(n^2). C'est une méthode de tri stable. L'algorithme d'insertion divise le tableau à trier en deux parties : la première partie contient tous les éléments du tableau, sauf le dernier élément (ce qui fait au tableau un espace de plus pour avoir une position d'insertion), et la deuxième partie ne contient que celui-ci. élément (c’est-à-dire l’élément à insérer). Une fois la première partie triée, ce dernier élément est inséré dans la première partie triée.

Principe

L'idée de base du tri par insertion directe (Tri par Insertion) est la suivante : chaque fois qu'un enregistrement à trier est inséré dans l'enregistrement précédemment trié selon sa taille de clé La position appropriée dans la sous-séquence ordonnée jusqu'à ce que tous les enregistrements soient insérés.

Supposons que le tableau soit un[0…n-1].

1. Initialement, a[0] forme une zone ordonnée, et la zone non ordonnée est a[1..n-1]. Soit i=1

2. Fusionnez a[i] dans la zone ordonnée actuelle a[0...i-1] pour former un intervalle ordonné de a[0...i].
3.i++ et répétez la deuxième étape jusqu'à ce que i==n-1. Tri terminé.

Implémentation du code PHP

function insertSort($arr){
  //获取需要排序的长度
  $length=count($arr);
  //假定第一个为有序的，所以从$i开始比较
  for ($i=1; $i <$length ; $i++) {
    //存放待比较的值
    $tmp=$arr[$i];
    for($j=$i-1;$j>=0;$j--){
      //若插入值比较小，则将后面的元素后移一位，并将值插入
      if($tmp<$arr[$j]){
        $arr[$j+1]=$arr[$j];
        $arr[$j]=$tmp;
      }else{
        break;
      }
    }
  }
  return $arr;
}

Calcul de la complexité temporelle de l'algorithme

Dans le meilleur des cas (les éléments ont Organiser les order) : Ensuite, vous n'avez besoin de boucler que n-1 fois, et la complexité temporelle est O(n)

Dans le pire des cas (les éléments sont dans l'ordre inverse) : le nombre d'ajustements de boucle doit être : [ n * (n -1) ]/2, la complexité temporelle est O (n ^ 2)
La complexité temporelle moyenne est : O (n ^ 2)

Ce qui précède est tout le contenu de cet article , J'espère que cela sera utile à l'apprentissage de tout le monde. C'est utile et j'espère que tout le monde soutiendra le site Web chinois php.

Articles qui pourraient vous intéresser :

Explication de l'algorithme de tri des seaux en PHP

Explication détaillée des problèmes rencontrés lors du développement et de la configuration du chargement différé dans le fournisseur de services Laravel

PHP implémente un algorithme de tri par tas

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!