Apprentissage de l'algorithme de tri par sélection simple PHP

Cet article présente principalement en détail l'algorithme PHP Simple Selection Sort, qui a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Les exemples de cet article sont partagés avec vous. le tri de sélection est pour votre référence. Le contenu spécifique est le suivant

Idée de base :

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

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.

Ce blog est référencé à partir de "Dahua Data Structure". Il n'est enregistré ici que pour référence future.

Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. J'espère également que tout le monde soutiendra le site Web php chinois.

Articles qui pourraient vous intéresser :

Explication détaillée de l'implémentation du code PHP WeChat Tiaoyitiao

Explication de la fonction de partage de WeChat vers Moments et d'enregistrement du nombre de partages mis en œuvre par PHP

Explication de l'exemple de classe d'outil de données au format XML d'analyse 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!