Comment implémenter un tri rapide en php

Comment implémenter le tri rapide en PHP : créez d'abord un exemple de fichier PHP ; puis créez la fonction d'échange et la fonction principale ; puis triez récursivement la sous-table basse et la sous-table haute ;

Recommandé : "Tutoriel vidéo PHP》

Idée de base :

Le tri rapide est une amélioration du tri à bulles. Son idée de base est de diviser les enregistrements à trier en deux parties indépendantes via un tri. Les mots-clés d'une partie sont plus petits que les mots-clés de l'autre partie de l'enregistrement. Les deux parties des enregistrements peuvent alors être rapidement triées séparément. L'ensemble du processus de tri peut être effectué de manière récursive pour atteindre l'objectif de commander la séquence entière.

Étapes de base de l'algorithme :

Par exemple :

Si l'enregistrement à trier maintenant est :

6   2   7   3   8   9

Première étape, Créez la variable $low pour pointer vers le premier enregistrement de l'enregistrement, $high pour pointer vers le dernier enregistrement, et $pivot comme valeur pivot pour être le premier élément de l'enregistrement à trier (pas nécessairement le premier), ici :

$low = 0;
$high = 5;
$pivot = 6;

La deuxième étape consiste à déplacer tous les nombres inférieurs à $pivot vers la gauche de $pivot, afin que nous puissions commencer à chercher des nombres inférieurs à 6, en commençant par $high, en regardant de droite vers la gauche, et continuons à décrémenter la valeur de la variable $high, nous constatons que la première donnée de l'indice 3 est inférieure à 6, nous déplaçons donc la donnée 3 vers la position de l'indice 0 (la position indiquée par $low), et déplaçons les données 6 à l'indice 0 à la position suivante. Mark 3, complétez la première comparaison :

3   2   7   6   8   9

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

La troisième étape, on commence la deuxième comparaison, cette fois il faut trouver celle plus grande que $. pivot, et nous devons chercher d’avant en arrière. Incrémentez la variable $low et constatez que les données à l'indice 2 sont les premières plus grandes que $pivot, nous utilisons donc les données 7 à l'indice 2 (la position pointée par $low) et les données 7 à l'indice 3 (la position pointée par $low). at by $high). 6 des données sont échangées et l'état des données devient le tableau suivant :

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

Terminer les deuxième et troisième étapes s'appelle terminer un cycle.

La quatrième étape (c'est-à-dire démarrer le cycle suivant) imite le processus de la deuxième étape.
La cinquième étape consiste à imiter le processus de la troisième étape.

Après l'exécution de la deuxième boucle, l'état des données est le suivant :

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

A cette étape, nous constatons que $low et $high "se rencontrent" : ils pointent tous les deux vers l'indice 2. Ainsi, la première comparaison est terminée. Le résultat est le suivant : tous les nombres à gauche de $pivot(=6) sont plus petits que lui, et tous les nombres à droite de $pivot sont plus grands que lui.

Ensuite, regroupez les données {3, 2} et {7, 8, 9} des deux côtés de , $pivot et effectuez le processus ci-dessus respectivement jusqu'à ce qu'aucun regroupement ne soit plus possible.

Remarque : Le premier passage de tri rapide n'obtiendra pas directement le résultat final, il divisera uniquement les nombres plus grands que k et plus petits que k des deux côtés de k. Afin d'obtenir le résultat final, vous devez refaire cette étape sur les tableaux des deux côtés de l'indice 2, puis décomposer le tableau jusqu'à ce que le tableau ne puisse plus être décomposé (une seule donnée) pour obtenir le résultat correct.

Implémentation de l'algorithme :

//交换函数
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

//主函数：
function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

Dans la fonction principale, puisque le premier passage du tri rapide trie l'ensemble du tableau, le point de départ est $low=0,$high=count($arr) - 1.
Ensuite, la fonction QSort() est un processus d'appel récursif, elle est donc encapsulée :

function QSort(array &$arr,$low,$high){
    //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);	//对低子表（$pivot左边的记录）进行递归排序
        QSort($arr,$pivot + 1,$high);	//对高子表（$pivot右边的记录）进行递归排序
    }
}

À partir de la fonction QSort() ci-dessus, nous pouvons voir que la fonction Partition() est le cœur de l'ensemble code , car la fonction de cette fonction est de sélectionner l'un des mots-clés, comme la sélection du premier mot-clé. Ensuite, nous faisons de notre mieux pour le placer dans une certaine position afin que les valeurs de gauche soient plus petites que lui et que les valeurs de droite soient plus grandes que lui. Nous appelons un tel mot-clé un pivot.

Aller directement au code :

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端

        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

L'ensemble du code combiné est le suivant :

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

On appelle l'algorithme :

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

Analyse de complexité :

Dans la situation optimale, c'est-à-dire si l'axe des nombres est choisi pour être à la valeur médiane de l'ensemble du tableau, le tableau sera divisé en deux moitiés à chaque fois. Par conséquent, la complexité temporelle dans le cas optimal est O(nlogn) (identique au tri par tas et au tri par fusion).

Dans le pire des cas, si la séquence à trier est dans l'ordre avant ou arrière, alors seules les données de bord peuvent être sélectionnées lors de la sélection du pivot. Chaque division entraînera un enregistrement de moins que la division précédente. une partition est vide, la complexité temporelle finale de ce cas est O(n^2).

Basée sur le meilleur et le pire des cas, la complexité temporelle moyenne est O(nlogn).

Le tri rapide est une méthode de tri instable.

Parce que le tri rapide est un tri relativement avancé et figure parmi les dix meilleurs algorithmes du 20e siècle. . . . Avec un algorithme aussi génial, pourquoi ne devrions-nous pas en tirer des leçons ?

Bien que cet algorithme soit déjà très bon, il reste encore des domaines à améliorer dans le programme d'algorithme ci-dessus.

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!