Partage d'exemples de tri par insertion de 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. Les amis intéressés peuvent s'y référer. J'espère qu'il pourra aider tout le monde.

Tri par insertion

Il existe une séquence de données déjà ordonnée, et il est nécessaire d'insérer un nombre dans cette séquence de données déjà triée, mais il est nécessaire que ces données séquence à insérer Toujours dans cet ordre, une nouvelle méthode de tri - la méthode de tri par insertion est utilisée. L'opération de base du tri par insertion consiste à insérer une donnée dans les données ordonnées triées, de manière à obtenir un nouveau numéro individuel plus un numéro ordonné. données, l'algorithme est adapté au tri d'une petite quantité de données et la complexité temporelle 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;
}

Algorithme de calcul de complexité temporelle

Dans le meilleur des cas (les éléments sont déjà dans l'ordre) : Ensuite, il vous suffit de boucler 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)

Recommandations associées :

Partage d'exemples d'algorithme de tri de seau d'implémentation PHP

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

Partage d'apprentissage de l'algorithme de tri par sélection simple PHP

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!