Algorithme de tri PHP Bubble Sort (Bubble Sort)

Cet article présente principalement la méthode d'implémentation de l'algorithme de tri Bubble Sort de PHP. Il fait référence à l'algorithme dans la structure de données Dahua et analyse en détail le principe et les techniques d'implémentation associées de Bubble Sort sous forme d'exemples. reportez-vous à

Cet article décrit la méthode d'implémentation du Bubble Sort (Bubble Sort) de l'algorithme de tri PHP à travers des exemples. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Idée de base :

Le tri à bulles est une sorte de tri par échange, son idée de base Oui : Comparez les mots-clés des enregistrements adjacents par paires, et s'ils sont dans l'ordre inverse, échangez-les jusqu'à ce qu'il n'y ait plus d'enregistrements dans l'ordre inverse.

L'implémentation de tri la plus simple :

Jetons d'abord un coup d'œil aux méthodes de tri souvent utilisées avant d'apprendre diverses méthodes de tri (au moins pour moi, c'est tout. . . . .

//这里使用了类型提示（type hint） array，不熟悉或者不习惯的同学大可去掉，不影响运算结果
function MySort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    for($j = $i + 1;$j < $length;$j ++){
      //将小的关键字放前面
      if($arr[$i] > $arr[$j]){
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
      }
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);

À proprement parler, le code ci-dessus n'est pas un tri à bulles standard, car ce n'est pas le cas. satisfaire l'idée de tri à bulles de "comparaison par paires d'enregistrements adjacents", il s'agit simplement d'un simple tri d'échange. L’idée est justement la suivante : en partant du premier mot-clé, comparez chaque mot-clé avec tous les mots-clés qui le suivent, et échangez-les pour obtenir la valeur minimale. Mais cet algorithme est très inefficace.

Algorithme de tri à bulles :

Il parcourt à plusieurs reprises le tableau à trier, en comparant deux éléments à la fois, s'ils sont dans le mauvais ordre. Échangez-les simplement. Le travail de visite du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié.

Le nom de cet algorithme vient du fait que les éléments plus grands du tableau « couleront » progressivement vers l'arrière du tableau après le tri, tandis que les éléments plus petits « flotteront » progressivement vers l'avant du tableau, d'où le nom.

L'algorithme de tri à bulles fonctionne comme suit : (de l'arrière vers l'avant)

1. Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-les tous les deux.

2. Faites le même travail pour chaque paire d'éléments adjacents, de la première paire au début à la dernière paire à la fin. À ce stade, le dernier élément doit être le plus grand nombre.
3. Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.
4. Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paires de nombres à comparer.

Vous ne le comprendrez peut-être pas si vous lisez la description textuelle, mais regardez le code :

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//冒泡排序
function BubbleSort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    //从后往前逐层上浮小的元素
    for($j = $length - 2;$j >= $i;$j --){
      //两两比较相邻记录
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
      }
    }
  }
}

Amélioration de l'algorithme de tri à bulles :

"Dahua Data Structure" est en effet un bon livre. Il nous présente également l'amélioration de l'algorithme de tri à bulles. copiez-le simplement ici. Déclaration :

L'algorithme de tri à bulles ci-dessus peut-il encore être optimisé ? La réponse est oui. Imaginez, si la séquence que nous voulons trier est {2,1,3,4,5,6,7,8,9}, c'est-à-dire qu'à l'exception du premier et du deuxième mot-clé, tout le reste doit être échangé . C'est déjà l'ordre normal. Lorsque i = 0, 2 et 1 sont échangés et la séquence à ce moment est déjà en ordre, mais l'algorithme exécute toujours i = 2 à 9 et la boucle j dans chaque boucle, bien qu'aucune donnée n'ait été échangée, mais les nombreuses comparaisons ceux qui ont suivi étaient en grande partie redondants.

Quand i = 2, nous avons comparé 9 et 8, 8 et 7, ·······, 3 et 2 sans aucun échange de données, ce qui signifie que cette séquence est déjà dans l'ordre. Il faut continuer. le travail de jugement ultérieur (aucun échange de données n'aura lieu dans le travail ultérieur et cela n'a aucun sens de le refaire). Afin de concrétiser cette idée, nous devons améliorer le code et ajouter une variable flag flag pour réaliser l'amélioration de cet algorithme :

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
/冒泡排序的优化(如果某一次循环的时候没有发生元素的交换，则整个数组已经是有序的了)
function BubbleSort1(array &$arr){
  $length = count($arr);
  $flag = TRUE;
  for($i = 0;($i < $length - 1) && $flag;$i ++){
    $flag = FALSE;
    for($j = $length - 2;$j >= $i;$j --){
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
        $flag = TRUE;
      }
    }
  }
}

La clé du changement de code est d'ajouter un jugement indiquant si l'indicateur est vrai dans la boucle for de la variable i. Après de telles améliorations, les performances du tri à bulles ont été améliorées, ce qui peut éviter le problème. problème d'être déjà en ordre. Jugement en boucle dénué de sens dans les situations.

La complexité temporelle totale de l'algorithme de bulle est

O(n^2).

Le tri à bulles est un tri stable.

Cet article est référencé à partir de "Dahua Data Structure". Il n'est enregistré ici que pour référence future.

Recommandations associées :

Algorithme de tri PHP Tri par sélection simple (Tri par sélection simple)

Algorithme de tri PHP Tri par insertion directe (insertion directe Trier)

Algorithme de tri PHP Shell Sort (Shell Sort)

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!