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);

Algorithme de tri à bulles :

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.

//交换方法
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 :

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;
      }
    }
  }
}

O(n^2).

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!