Un exemple de la façon d'implémenter le tri rapide de manière récursive 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. référez-vous à lui

L'exemple de cet article décrit la méthode d'implémentation du tri rapide de manière récursive en PHP. Partagez-le avec tout le monde pour votre référence, comme suit :

Tout d'abord, nous devons comprendre le principe du tri rapide : Trouver n'importe quel élément dans le tableau actuel (généralement, sélectionnez le premier élément), en standard, créez deux tableaux vides et parcourez tous les éléments du tableau. Si l'élément parcouru est plus petit que l'élément actuel, placez-le dans le tableau de gauche, sinon placez-le dans le tableau de droite. , puis faites de même avec la nouvelle opération de 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 le tableau est supérieur à 1, alors il doit être décomposé à nouveau, donc notre point de récursion est que le nombre d'éléments du tableau nouvellement construits est supérieur à 1

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

Comprenant le principe, jetons un coup d'œ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
)

PS : Voici un autre outil de démonstration pour le tri recommandé pour votre référence :

Démonstration d'animation en ligne des outils de processus d'algorithme d'insertion/sélection/bulle/fusion/Hill/tri rapide :
http://tools.jb51.net/aideddesign/paixu_ys

Articles qui pourraient vous intéresser :

Tutoriel détaillé sur la façon d'implémenter le déploiement de git en PHP

Exemple d'analyse et explication de l'algorithme de recherche binaire implémenté en PHP

Exemple d'analyse et explication de l'algorithme de recherche binaire implémenté en 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!