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

Cet article présente principalement en détail l'algorithme PHP Simple Selection Sort. Il a une certaine valeur de référence. Les amis intéressés peuvent s'y référer. J'espère qu'il pourra aider tout le monde.

L'exemple de cet article partage le code spécifique du tri par sélection simple en PHP pour votre référence. Le contenu spécifique est le suivant

Idée de base :

Passez n - Comparaison entre i mots-clés, sélectionnez l'enregistrement avec le plus petit mot-clé parmi n - i + 1 enregistrements et échangez-le avec l'enregistrement i (1 <= i <= n), en exécutant n-1 fois Puis le tri de la séquence d'enregistrements est terminé.

Implémentation 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);

Analyse de complexité :

en In Grâce au simple processus de tri par sélection, 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.

Recommandations associées :

Explication détaillée du tri par sélection directe dans la série d'algorithmes de tri PHP

Explication détaillée du tri par bucket dans l'algorithme de tri PHP compétences series_php

Analyse détaillée de la méthode d'implémentation de l'algorithme de tri Hill en 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!