Explication détaillée de l'utilisation du tri à bulles PHP

Cette fois, je vous apporte une explication détaillée de l'utilisation de PHP Bubble Sort, et quelles sont les Précautions lors de l'utilisation de PHP Bubble Sort. Ce qui suit est un cas pratique, allons-y. jetez un oeil.

Idée de base :

Le tri à bulles est une sorte de tri par échange. Son idée de base est la suivante : la clé pour comparer les enregistrements adjacents par paires de mots, en cas d'inversion, ils sont échangés jusqu'à ce qu'il n'y ait plus d'enregistrements dans l'ordre inversé.

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 considéré comme un tri à bulles standard, car il ne satisfait pas à l'idée de tri de "comparaison par paires d'enregistrements adjacents". juste un simple é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 du texte, 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 des bulles :

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 un indicateur de variable de marque 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 le boucle for de la variable i Dans , le jugement indiquant si le drapeau est vrai est ajouté. Après une telle amélioration, les performances du tri des bulles ont été améliorées et le jugement de boucle dénué de sens peut être évité lorsque l'ordre est déjà en ordre. .

La complexité temporelle totale de l'algorithme de bulle est O(n^2).

Le tri à bulles est un tri stable.

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Analyse de cas de tri PHP Hill

Analyse d'un exemple d'algorithme de tri de tas 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!