Maison  >  Article  >  développement back-end  >  Principe de tri rapide PHP, méthode de mise en œuvre et exemple d'analyse

Principe de tri rapide PHP, méthode de mise en œuvre et exemple d'analyse

墨辰丷
墨辰丷original
2018-06-02 10:00:021366parcourir

Cet article présente principalement le principe et la méthode de mise en œuvre du tri rapide PHP, et analyse le principe de l'algorithme et les techniques spécifiques de mise en œuvre du tri rapide PHP sous forme d'exemples. Les amis dans le besoin peuvent se référer à

Les détails. sont les suivantes :

<?php
$n = array(&#39;13&#39;,&#39;14&#39;,&#39;55&#39;,&#39;10&#39;,&#39;54&#39;,&#39;2&#39;,&#39;79&#39;,&#39;106&#39;,&#39;89&#39;,&#39;90&#39;,&#39;22&#39;,&#39;60&#39;,&#39;111&#39;,&#39;77777&#39;,&#39;-110&#39;,&#39;-10&#39;,&#39;123&#39;);
function partition($n,$left,$right)
{
  global $n;
  $pivot = $n[$left];
  $lo=$left;
  $hi=$right+1;
  while($lo+1!=$hi) {
    if($n[$lo+1]<$pivot)
      $lo++;
    else if($n[$hi-1]>$pivot)
      $hi--;
    else{
      $t=$n[$lo+1];
      $n[$lo+1]=$n[$hi-1];
      $n[$hi-1]=$t;
      $lo++;
      $hi--;
    }
  }
  $n[$left]=$n[$lo];
  $n[$lo]=$pivot;
  return $lo;
}
function quicksort($n,$left,$right)
{
  global $n;
  $dp = 0;
  if ($left<$right) {
     $dp=partition($n,$left,$right);
     quicksort($n,$left,$dp-1);
     quicksort($n,$dp+1,$right);
  }
}
quicksort($n,0,sizeof($n)-1);
print_r($n);
?>

Le tri rapide est une amélioration du tri à bulles. Son idée de base est de diviser les données à trier en deux parties indépendantes grâce à un tri unidirectionnel. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis les deux parties des données sont triées séquentiellement. Pour un tri rapide, l'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée.

En supposant que le tableau à trier est A[1]...A[N], sélectionnez d'abord au hasard une donnée (généralement la première donnée) comme donnée clé, puis mettez tous les nombres plus petits qu'elle Devant lui, tous les nombres plus grands sont placés derrière lui. Ce processus est appelé tri rapide à une position. L'algorithme de tri rapide est :

1). Définissez deux variables I et J. Lorsque le tri commence, I:=1, J:=N
2). , l'élément est attribué à X, c'est-à-dire une valeur inférieure à Exchange
5), répétez les étapes 3 et 4 jusqu'à ce que I=J

Le tri rapide consiste à appeler ce processus de manière récursive - diviser le séquence de données avec 49 comme point médian, et séparez la partie précédente Effectuez un tri rapide similaire à la dernière partie pour terminer le tri rapide de toutes les séquences de données, et enfin transformez cette séquence de données en une séquence ordonnée

Résumé : Ce qui précède représente l’intégralité du contenu de cet article, j’espère que cela pourra aider l’apprentissage de chacun.

Recommandations associées :

phpExplication détaillée des exemples d'accès au développement WeChat

php Explication détaillée de l'exemple d'accès au développement WeChat

PHP+MySQL réalise une requête floue de la fonction d'information sur les employés

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