Explication détaillée du cas de tri par sélection simple PHP

Cette fois, je vais vous apporter une explication détaillée du cas tri par sélection simple PHP , et quelles sont les précautions pour le tri par sélection simple PHP Ce qui suit est un cas pratique, jetons un coup d'oeil.

Idée de base :

Sélectionnez la clé parmi n - i + 1 enregistrements via n - i comparaisons entre mots-clés L'enregistrement avec le plus petit mot est échangé avec le i-ième (1 <= i <= n) enregistrement Après avoir exécuté n-1 fois, le tri de la séquence d'enregistrements est terminé.

Mise en œuvre de l'algorithme :

<?php
//简单选择排序
//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//简单选择排序算法
function SelectSort(array &$arr){
  $count = count($arr);
  for($i = 0;$i < $count - 1;$i ++){
    //记录第$i个元素后的所有元素最小值下标
    $min = $i;
    for($j = $i + 1;$j < $count;$j ++){
      if($arr[$j] < $arr[$min]){
        $min = $j;
      }
    }
    if($min != $i){
      swap($arr,$min,$i);
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
SelectSort($arr);
var_dump($arr);

Résultat d'exécution :

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

Analyse de complexité :

Dans le processus de tri par sélection simple, le nombre d'enregistrements à déplacer est relativement faible. Dans le meilleur des cas, c'est-à-dire que l'état initial des enregistrements à trier est déjà dans l'ordre positif et qu'il n'est pas nécessaire de déplacer les enregistrements.

Dans le pire des cas, c'est-à-dire que l'état initial des enregistrements à trier est que le premier enregistrement est le plus grand, et les enregistrements suivants sont classés par ordre croissant, puis le nombre d'enregistrements qui doivent être déplacé est au plus 3 (n-1). Le nombre de comparaisons requises lors du tri par sélection simple n'a rien à voir avec la disposition de la séquence d'enregistrements à trier dans l'état initial. Lorsque i=1, n-1 comparaisons sont requises ; lorsque i=2, n-2 comparaisons sont requises et ainsi de suite, le nombre total de comparaisons requises est (n-1)+(n-2)+ …+2 ; +1=n(n-1)/2, c'est-à-dire que la complexité temporelle de l'opération de comparaison est O(n^2), et la complexité temporelle de l'opération de déplacement est O(n) .

Le tri par sélection simple est un tri instable.

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 :

Explication détaillée des étapes pour utiliser l'algorithme de tri rapide PHP

Explication détaillée des étapes pour utiliser le tri par base 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!