Exemple de comment implémenter le tri rapide en PHP

Cet article présente principalement la méthode d'implémentation récursive PHP du tri rapide. Il décrit brièvement le principe du tri rapide et analyse les compétences opérationnelles pertinentes de PHP en utilisant des algorithmes récursifs pour implémenter le tri rapide sous forme d'exemples. je peux m'y référer. J'espère que cela pourra aider tout le monde.

Tout d'abord, il faut comprendre le principe du tri rapide : rechercher n'importe quel élément du tableau courant (en général choisir le premier élément), en standard, créer deux tableaux vides, parcourir l'ensemble des éléments du tableau, s'il est traversé vers Si l'élément est plus petit que l'élément actuel, placez-le dans le tableau de gauche, sinon placez-le dans le tableau de droite, puis effectuez la même opération sur le nouveau tableau.

Il n'est pas difficile de trouver que cela est cohérent avec le principe de récursivité, nous pouvons donc utiliser la récursivité pour l'implémenter.

Pour utiliser la récursion, vous devez trouver le point de récursion et la sortie de récursion :

Point de récursion : Si les éléments du tableau sont supérieurs à 1, il doit être à nouveau décomposé, donc notre le point de récursion est le tableau nouvellement construit Le nombre d'éléments est supérieur à 1

Sortie récursive : Quand n'a-t-on plus besoin de trier le nouveau tableau ? C'est à ce moment-là que le nombre d'éléments du tableau devient 1, c'est donc notre sortie.

Comprenez le principe, jetons un œil à l'implémentation du code~

<?php
//快速排序
//待排序数组
$arr=array(6,3,8,6,4,2,9,5,1);
//函数实现快速排序
function quick_sort($arr)
{
    //判断参数是否是一个数组
    if(!is_array($arr)) return false;
    //递归出口:数组长度为1，直接返回数组
    $length=count($arr);
    if($length<=1) return $arr;
    //数组元素有多个,则定义两个空数组
    $left=$right=array();
    //使用for循环进行遍历，把第一个元素当做比较的对象
    for($i=1;$i<$length;$i++)
    {
      //判断当前元素的大小
      if($arr[$i]<$arr[0]){
        $left[]=$arr[$i];
      }else{
        $right[]=$arr[$i];
      }
    }
    //递归调用
    $left=quick_sort($left);
    $right=quick_sort($right);
    //将所有的结果合并
    return array_merge($left,array($arr[0]),$right);
}
//调用
echo "<pre class="brush:php;toolbar:false">";
print_r(quick_sort($arr));

Résultats d'exécution :

Array
(
  [0] => 1
  [1] => 2
  [2] => 3
  [3] => 4
  [4] => 5
  [5] => 6
  [6] => 6
  [7] => 8
  [8] => 9
)

Recommandations associées :

JS Comment implémenter le tri Hill et le tri rapide

Exemple d'implémentation d'un algorithme de tri rapide pour les tableaux bidimensionnels en PHP

Comment mettre en place un tri rapide

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!