Detaillierte Erläuterung der Anwendungsbeispiele von Quicksort in PHP

Dieser Artikel stellt hauptsächlich die Implementierungsmethode von PHP Quick Sort Quick vorksort Es analysiert das Prinzip der schnellen Sortierung und die damit verbundenen Betriebsfähigkeiten von PHP, um die schnelle Sortierung in Form von Beispielen zu implementieren es kann darauf verweisen

Das Beispiel in diesem Artikel beschreibt PHP Quicksort Quicksort. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Schnellsortierung

Im Schnellsortierungsalgorithmus wird die Divide-and-Conquer-Strategie verwendet. Zuerst wird die Sequenz in zwei Teilsequenzen unterteilt und rekursiv die Teilsequenzen sortiert, bis die gesamte Sequenz sortiert ist. (d. h. die Idee, es in zwei Teile zu teilen)

Die Schritte sind wie folgt:

Wählen Sie ein Schlüsselelement in der Sequenz als Achse aus;

Passen Sie die Reihenfolge neu an, verschieben Sie Elemente, die kleiner als die Achse sind, nach vorne und Elemente, die größer als die Achse sind, nach hinten. Nach der Division befindet sich die Achse an ihrer endgültigen Position;

ordnet rekursiv zwei Teilfolgen neu: die Teilfolge mit kleineren Elementen und die Teilfolge mit größeren Elementen.

Zum Beispiel die Sequenz $arr:

5 3 0 11 44 7 23 2 Setzen Sie das erste Element $arr[0] = 5 als Achse und setzen Sie das Flag auf niedrig. .. top stellt den Anfang und das Ende dar
2 3 0 11 44 7 23 2 Beginnen Sie den Vergleich aus der entgegengesetzten Richtung (rechts): 22 3 0 11 44 7 23 11 Starten Sie den Vergleich von der entgegengesetzten Richtung (links), bis :5 Wiederholen Sie die obigen Schritte, bis niedrig == oben. Ersetzen Sie die Position durch das Achsenelement , also 5
2 3 0 5 44 7 23 11
Auf diese Weise kann es in zwei Teile geteilt werden: 2 3 0 und 44 23 11
Auf diese Weise können wir den rekursiven Fortsetzungsstartschritt erhalten

Algorithmusimplementierung:

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;
    }
}

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Anwendungsbeispiele von Quicksort in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!