Comment implémenter un algorithme de tri rapide non récursif en PHP

Introduction

Le tri rapide est un algorithme de tri efficace qui réalise le tri en divisant continuellement un tableau en deux sous-tableaux. Dans l'algorithme de tri rapide, une valeur pivot est sélectionnée et tous les éléments inférieurs à la valeur pivot sont placés sur son côté gauche, tandis que tous les éléments supérieurs à la valeur pivot sont placés sur son côté droit. Ce processus est ensuite appliqué de manière récursive aux sous-tableaux gauche et droit jusqu'à ce que l'ensemble du tableau soit trié.

Le tri rapide est une fonction récursive, car elle doit décomposer le problème d'origine en deux sous-problèmes plus petits, puis résoudre le problème d'origine en résolvant ces sous-problèmes de manière récursive. Bien que cette approche puisse fonctionner efficacement dans certaines situations, elle présente certaines limites. Plus précisément, lors du traitement de grands tableaux, les algorithmes récursifs peuvent épuiser l'espace de pile de l'ordinateur, provoquant une exception de débordement de pile. De plus, la surcharge supplémentaire liée aux appels de fonctions récursifs peut également entraîner une dégradation des performances de l'algorithme.

Par conséquent, dans certains cas, il peut être plus approprié d'utiliser des méthodes d'implémentation non récursives. Dans cet article, nous présenterons un algorithme non récursif pour un tri rapide utilisant PHP.

Implémentation de l'algorithme

Nous définissons d'abord une partition de fonction auxiliaire, qui est utilisée pour diviser un tableau en deux sous-tableaux : un contenant tous les éléments plus petits que la valeur de base et un contenant tous les éléments supérieurs à la valeur de base.

function partition(&$arr, $left, $right) {
    $pivot = $arr[$right]; // 选择最后一个元素作为基准值
    $i = $left - 1;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]); // 交换i和j处的元素
        }
    }
    list($arr[$i + 1], $arr[$right]) = array($arr[$right], $arr[$i + 1]); // 将基准值放到正确的位置
    return $i + 1;
}

Cette fonction sélectionne le dernier élément du tableau comme valeur de base et place tous les éléments plus petits que la valeur de base sur le côté gauche du tableau en échangeant les éléments du tableau. Dans ce processus, nous utilisons la variable $i pour enregistrer l'indice du sous-tableau actuellement traité, et $j est utilisé pour parcourir l'ensemble du tableau. Lorsque nous trouvons un élément plus petit que la valeur pivot, nous déplaçons $i d'une position vers la droite et plaçons l'élément à la position de $i. Enfin, nous plaçons la valeur de base à la position finale $i + 1.

Avec la fonction de partition, nous pouvons désormais implémenter une version non récursive de l'algorithme de tri rapide. Dans cette version, nous utilisons une pile pour stocker les sous-tableaux à traiter. Lorsque nous traitons un sous-tableau, nous enregistrons d'abord les limites gauche et droite du sous-tableau sur la pile, puis continuons à le diviser en deux sous-tableaux plus petits jusqu'à ce que tous les sous-tableaux soient triés.

function quick_sort(&$arr) {
    $stack = new SplStack(); // 使用SplStack实现栈
    $stack->push(count($arr) - 1); // 将整个数组的下标压入栈
    $stack->push(0);
    while (!$stack->isEmpty()) {
        $left = $stack->pop();
        $right = $stack->pop();
        $pivotIndex = partition($arr, $left, $right);
        if ($left < $pivotIndex - 1) {
            $stack->push($pivotIndex - 1);
            $stack->push($left);
        }
        if ($pivotIndex + 1 < $right) {
            $stack->push($right);
            $stack->push($pivotIndex + 1);
        }
    }
}

Dans cette version du code, nous utilisons la classe SplStack pour implémenter la pile. Nous poussons d'abord les limites gauche et droite de l'ensemble du tableau sur la pile, puis supprimons continuellement les limites gauche et droite de la pile et les transmettons à la fonction de partition pour diviser le sous-tableau. Si left < pivotIndex - 1, cela signifie que le sous-tableau de gauche n'est pas encore trié et est poussé sur la pile pour attendre le traitement. De même, si pivotIndex + 1 right <, cela signifie que le sous-tableau de droite n'est pas encore trié et est placé sur la pile pour traitement.

La complexité temporelle de cet algorithme est O(nlogn). Bien qu'il ne soit pas aussi rapide que la version récursive du tri rapide dans tous les cas, il peut réduire considérablement la complexité spatiale de l'algorithme et éviter la surcharge des appels de fonctions récursifs. Si vous avez besoin de trier rapidement un grand tableau en PHP, cet algorithme peut mieux répondre à vos besoins que la version récursive du 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!