Maison >développement back-end >tutoriel php >Compétences PHP : analyse d'un exemple d'algorithme de tri rapide PHP

Compétences PHP : analyse d'un exemple d'algorithme de tri rapide PHP

无忌哥哥
无忌哥哥original
2018-07-12 14:17:111425parcourir

Cet article présente principalement l'algorithme de tri rapide PHP, et analyse les principes, les étapes et les définitions PHP associées et les techniques d'utilisation du tri rapide sous forme d'exemples. Les amis dans le besoin peuvent s'y référer

Les exemples. dans cet article, décrivez l'algorithme de tri rapide PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Tri rapide : dans le tableau non ordonné $data, sélectionnez n'importe quelle valeur comme valeur de comparaison, définissez i comme index de récupération de tête, j comme queue indice de récupération,

Étapes de l'algorithme :

(1) Initialiser les valeurs de contraste $value=$data[0], $i=1, $j=count($data)-1

( 2) Commencez par la queue Commencez la récupération et déterminez si $data[$j] est plus petit que $value Si ce n'est pas le cas, alors $j-- continuez la récupération jusqu'à ce que les coordonnées $value

soient inférieures à

. ) À ce moment, lancez la récupération de la tête et déterminez si $data[$i] est supérieur à $value, sinon, alors $i++, continuez la recherche jusqu'à ce qu'une coordonnée $value

plus grande que

soit trouvée (4) À l'heure actuelle, les valeurs de $data[$j] et $data[$i] s'excluent mutuellement. Swap, c'est-à-dire mettre celui plus grand que $value à droite et mettre celui plus petit que $value à gauche

(5) Répétez 3 et 4 jusqu'à $i==$j

(6) A ce moment, ceux plus grands que $value ont été placés à droite, et ceux plus petits que $value ont a été placé à gauche. La position des coordonnées au milieu est déterminée comme étant $i, la valeur du milieu est $value et la valeur de $data[$i] est combinée avec l'échange de valeur $data[0], car la valeur du milieu est $value, vous devez déplacer $value vers la coordonnée médiane du tableau

(7) Le tableau est divisé en deux tableaux non ordonnés à gauche et à droite, puis exécuter récursivement 1 à 6, jusqu'à ce que le la longueur du tableau est de 1

Conseils : La définition chinoise du tri rapide sera plus claire dans Baidu

Code :

<?php
header("Content-type: text/html; charset=utf-8");
function quickSort($data, $startIndex, $endIndex){
 if($startIndex < $endIndex){
  $value = $data[$startIndex]; // 对比值
  $startT = $startIndex + 1;
  $endT = $endIndex;
  while ($startT != $endT) {
   // 找到比对比值小的坐标
   while ($data[$endT] > $value && $endT > $startT){
    $endT--;
   }
   // 找到比对比值大的左边
   while ($data[$startT] < $value && $startT < $endT){
    $startT++;
   }
   if($endT > $startT){
    $temp =$data[$startT];
    $data[$startT] = $data[$endT];
    $data[$endT] = $temp;
   }
  }
  // 防止数组已经排序好的情况
  if($data[$startT] < $value){
   $data[$startIndex] = $data[$startT];
   $data[$startT] = $value;
  }
  $data = quickSort($data, $startIndex, $startT - 1);
  $data = quickSort($data, $startT + 1, $endIndex);
  return $data;
 }else{
  return $data;
 }
}
$data = array(10, 5, 30, 22, 1, 42, 14, 34, 8, 13, 28, 36, 7);
$data = quickSort($data, 0, count($data) - 1);
var_dump($data);

Résultat de l'exécution :

array(13) {
  [0]=>
  int(1)
  [1]=>
  int(5)
  [2]=>
  int(7)
  [3]=>
  int(8)
  [4]=>
  int(10)
  [5]=>
  int(13)
  [6]=>
  int(14)
  [7]=>
  int(22)
  [8]=>
  int(28)
  [9]=>
  int(30)
  [10]=>
  int(34)
  [11]=>
  int(36)
  [12]=>
  int(42)
}

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn