Explication détaillée du tri par sélection directe des séries d'algorithmes de tri PHP

Cet article présente principalement en détail les informations pertinentes sur le tri par sélection directe de la série d'algorithmes de tri PHP. J'espère que cela pourra aider tout le monde.

Tri par sélection directe

L'idée de base du tri par sélection directe est la suivante : sélectionnez d'abord parmi R[0]~R[n-1] Sélectionnez la valeur minimale , échangez-le avec R[0], sélectionnez la valeur minimale de R[1]~R[n-1] pour la deuxième fois, échangez-le avec R[1], ...., sélectionnez la valeur minimale de R[ i-1] pour la ième fois ]~R[n-1], sélectionner la valeur minimale, l'échanger avec R[i-1], ....., sélectionner la valeur minimale parmi R[n-2]~ R[n-1] pour la n-1ère fois, échangez avec R[n-2], passez n-1 fois au total et obtenez une séquence ordonnée classée du petit au grand par code de tri·

Le principal avantage du tri par sélection est lié au mouvement des données. Si un élément est dans la bonne position finale, il ne sera pas déplacé. Chaque fois que le tri par sélection échange une paire d'éléments, au moins l'un d'entre eux sera déplacé vers sa position finale, donc le tri d'une liste de n éléments nécessite au plus n-1 échanges. Parmi toutes les méthodes de tri qui reposent entièrement sur l’échange pour déplacer des éléments, le tri par sélection est une très bonne méthode.

Principe

Trouvez d'abord le plus petit (grand) élément de la séquence non triée, stockez-le à la position de départ de la séquence triée, puis sélectionnez-le parmi les éléments restants éléments non triés. Continuez à rechercher l’élément le plus petit (le plus grand) et placez-le à la fin de la séquence triée. Et ainsi de suite jusqu'à ce que tous les éléments soient triés.

Exemple

Supposons que le tableau soit un[0...n-1].
1. Initialement, le tableau n'est pas ordonné et la zone est a[0..n-1]. Soit i=0
2. Sélectionnez le plus petit élément de la zone non ordonnée a[i...n-1] et échangez-le avec a[i]. Après l'échange, a[0...i] forme une zone ordonnée.
3.i++ et répétez la deuxième étape jusqu'à ce que i==n-1. Tri terminé.

Exemple

Trier le tableau [53,89,12,98,25,37,92,5]

Première prise i= 0 ;a[i] est la valeur minimale. Comparez la valeur suivante avec a[i]. Si elle est inférieure à a[i], échangez la position avec a[i], $i++

[5, 89 ,53,98,25,37,92,12]

Prenons d'abord i=1;a[i] comme valeur minimale, comparez la valeur suivante avec a[i], si elle est inférieure à a[i] petit, échangez des positions avec a[i], $i++

[5,12,89,98,53,37,92,25]

Répétez les étapes ci-dessus

Implémentation du code PHP

function select_sort($arr){
  $length=count($arr);
  for ($i=0; $i <$length-1 ; $i++) {
    for ($j=$i+1,$min=$i; $j <$length ; $j++) {
      if ($arr[$min]>$arr[$j]) {
        $min=$j;
      }
    }
    $temp=$arr[$i];
    $arr[$i]=$arr[$min];
    $arr[$min]=$temp;
  }
  return $arr;
}

Recommandations associées :

Explication détaillée du tri par fusion de l'algorithme de tri PHP

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

Apprentissage des algorithmes de tri courants 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!