Algorithme de tri PHP Simple Selection Sort (Simple Selection Sort)

Cet article présente principalement l'algorithme de tri PHP Simple Selection Sort. Il analyse en détail les principes et les techniques de mise en œuvre associées de l'algorithme Simple Selection Sort sous forme d'exemples. Les amis dans le besoin peuvent s'y référer

. L'exemple de cet article décrit l'algorithme de tri PHP Simple Selection Sort. Partagez-le avec tout le monde pour votre référence, comme suit :

Idée de base :

Grâce à n - i comparaisons entre mots-clés, à partir de n - Sélectionnez l'enregistrement avec le plus petit mot-clé parmi les i + 1 enregistrements et l'échanger avec l'enregistrement i (1 <= i <= n) Après avoir exécuté n-1 fois, 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);

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 mouvement requis des enregistrements le nombre de fois 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.

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 insertion directe (Tri par insertion droite)

Algorithme de tri PHP Tri par colline (Tri par Shell)

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!