Explication détaillée des exemples d'utilisation du tri rapide en php

Cet article présente principalement la méthode d'implémentation du tri rapide PHPksort. Il analyse le principe du tri rapide et les compétences opérationnelles associées de PHP pour implémenter le tri rapide sous forme d'exemples. peut s'y référer

L'exemple de cet article décrit le tri rapide PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

tri rapide

Dans l'algorithme de tri rapide, la stratégie diviser pour régner est utilisée. Tout d'abord, la séquence est divisée en deux sous-séquences, et récursivement trie les sous-séquences jusqu'à ce que la séquence entière soit triée. (c'est-à-dire l'idée de le diviser en deux)

Les étapes sont les suivantes :

Sélectionner un élément clé de la séquence comme axe

Ajustez la séquence Réorganisez, déplacez les éléments plus petits que l'axe vers l'avant de l'axe et déplacez les éléments plus grands que l'axe vers l'arrière de l'axe. Après la division, l'axe est à sa position finale ;

réordonne récursivement deux sous-séquences : la sous-séquence avec des éléments plus petits et la sous-séquence avec des éléments plus grands.

Par exemple, la séquence $arr:

5 3 0 11 44 ​​​​​7 23 2 Définissez le premier élément $arr[0] = 5 comme axe pour définir le drapeau bas. .. top représente le début et la fin
2 3 0 11 44 ​​​​​7 23 2 Commencez la comparaison dans la direction opposée (à droite) : 2<5 Remplacez la première position par 2, low++
2 3 0 11 44 ​​​​​7 23 11 Commencez la comparaison dans la direction opposée (gauche) jusqu'à :5<11 Remplacez la dernière position par 11, top–
Répétez les étapes ci-dessus jusqu'à ce que low == top Remplacez la position par l'élément d'axe , qui est 5
2 3 0 5 44 7 23 11
De cette façon Peut être divisé en deux parties 2 3 0 et 44 23 11
De cette façon, nous pouvons obtenir l'étape de départ de la suite récursive

Mise en œuvre de l'algorithme :

class quick_sort{
    function quicksort(&$arr,$low,$top){
      if($low < $top){
        $pivotpos = $this->partition($arr,$low,$top);
        $this->quicksort($arr,$low,$pivotpos-1);
        $this->quicksort($arr,$pivotpos+1,$top);
      }
    }
    function partition(&$arr, $low ,$top){
      if($low == $top){
        return;
      }
  //   设置初始数值
      $com = $arr[$low];
      while($low!=$top){
  //      将比初始数值小的替换到左边
        while($top&&$top!=$low){
          if($com > $arr[$top]){
          $arr[$low++] = $arr[$top];
          break;
          }else{
            $top--;
          }
        }
  //      将比初始数值大的替换到右边
        while($low&&$low!=$top){
          if($com < $arr[$low]){
            $arr[$top--] = $arr[$low];
            break;
          }else{
            $low++;
          }
        }
      }
      $arr[$low] = $com;
      return $low;
    }
}

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!