PHP Quicksort Quicksort-Beispiel, ausführliche Erklärung

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 die Teilsequenzen werden rekursiv sortiert, bis die gesamte Sequenz sortiert ist. (Das heißt, 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;

Neu anordnen Die Reihenfolge ändern und die Achse ändern. Kleine Elemente werden an die Vorderseite der Achse verschoben, und Elemente, die größer als die Achse sind, werden an die Rückseite der Achse verschoben. Nach der Division befindet sich die Achse an ihrer endgültigen Position.

ordnet rekursiv zwei Teilsequenzen neu: die Teilsequenz mit kleineren Elementen und die Teilsequenz mit größeren Elementen.

Zum Beispiel die Sequenz $arr:

5 3 0 11 44 7 23 2 Legen Sie das erste Element $arr[0] = 5 als Achse fest, um das Flag auf niedrig zu setzen. .. 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): 2<5 Ersetzen Sie die erste Position durch 2, low++
2 3 0 11 44 7 23 11 Starten Sie den Vergleich von der entgegengesetzten Richtung (links), bis :5<11 Ersetzen Sie die letzte Position durch 11, oben–
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

Algorithmus-Implementierung:

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

Ich hoffe, dass dieser Artikel für alle in der PHP-Programmierung hilfreich sein wird.

Ausführlichere Erläuterungen zu PHP-Quicksort-Quicksort-Beispielen und verwandten Artikeln finden Sie auf der chinesischen PHP-Website!