Quick Sort ist einer der effizientesten Algorithmen und verwendet die Divide-and-Conquer-Technik zum Sortieren von Arrays.

So funktioniert die Schnellsortierung

Die Hauptidee von Quick Sort besteht darin, einem Element nach dem anderen dabei zu helfen, an die richtige Position in einem unsortierten Array zu gelangen. Dieses Element wird Pivot genannt.

Das Drehelement befindet sich in der richtigen Position, wenn:

1. Alle Elemente links davon sind kleiner.
2. Alle Elemente rechts davon sind gr??er.

Es spielt keine Rolle, ob die Zahlen links oder rechts schon sortiert sind. Wichtig ist, dass sich der Drehpunkt an der richtigen Position im Array befindet.

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

All dies sind gültige Ausgaben eines Arrays, bei dem der Pivot 23 ist.

Die richtige Position des Drehpunkts finden

Quick Sort hilft dem Pivot, seine richtige Position im Array zu finden. Wenn sich der Pivot beispielsweise am Anfang des Arrays befindet, aber nicht die kleinste Zahl ist, bestimmt Quick Sort, dass er sich um 5 Schritte bewegen muss, um Platz für die 5 kleineren Elemente im Array zu schaffen – vorausgesetzt, es gibt 5 solcher Elemente Zahlen.

Nehmen wir an, wir haben das Array: [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] und 10 ist der Drehpunkt:

An diesem Punkt:

• Die Nummer 10 wei? nicht, ob sie sich an der richtigen Position befindet und wie viele Schritte sie zurücklegen muss, um dorthin zu gelangen. Quick Sort beginnt mit dem Vergleich von 10 mit dem Wert am n?chsten Index.
• Wenn Quick Sort erkennt, dass 4 kleiner ist, zeichnet es auf, dass sich der Pivot einen Schritt nach vorne bewegen muss, damit 4 davor kommen kann.
• Also numberOfStepsToMove erh?ht sich um 1.

Als n?chstes betr?gt der Wert bei Index 2 15, was gr??er als 10 ist. Da keine Anpassung erforderlich ist, Schnellsortierung beh?lt die Schrittanzahl unver?ndert bei und geht zum n?chsten Element im Array über.

Beim n?chsten Index ist der Wert 6, was kleiner als 10 ist. Quick Sort erh?ht die Schrittzahl auf 2, da der Pivot nun Platz für zwei kleinere Zahlen schaffen muss: 4 und 6 .

Jetzt muss 6 durch 15 ersetzt werden, damit die kleineren Zahlen auf der linken Seite des Arrays nebeneinander bleiben. Wir tauschen die Zahlen basierend auf den aktuellen Index- und numberOfStepsToMove-Werten aus.

Quick Sort durchl?uft weiterhin das Array und erh?ht die Zahl ?NumberOfStepsToMove“ basierend darauf, wie viele Zahlen kleiner als der Pivot sind. Dadurch l?sst sich ermitteln, wie weit sich der Drehpunkt in die richtige Position bewegen muss.

Die numberOfStepsToMove ?ndert sich bei 23 oder 40 nicht, da beide Werte gr??er als der Pivot sind und im Array nicht davor stehen sollten:

Wenn Quick Sort nun eine Schleife zum Wert 1 an Index 6 durchl?uft, erh?ht sich numberOfStepsToMove auf 3 und tauscht die Zahl an Index 3 aus:

Quick Sort setzt diesen Vorgang fort, bis das Ende des Arrays erreicht ist:

Da wir nun das Ende des Arrays erreicht haben, wissen wir, dass es 5 Zahlen gibt, die kleiner als 10 sind. Daher muss sich der Drehpunkt (10) 5 Schritte nach vorne zu seiner richtigen Position bewegen, wo er gr??er als alle ist Zahlen davor.

Mal sehen, wie das im Code aussieht:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Da wir nun eine Funktion haben, die uns hilft, die Position des Pivots zu finden, sehen wir uns an, wie Qucik Sort das Array in kleinere Arrays aufteilt und die Funktion getNumberOfStepsToMove verwendet, um alle Array-Elemente zu platzieren.

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

Schnellsortierung nutzt Rekursion, um das Array effizient in kleinere Unterarrays zu unterteilen und sicherzustellen, dass Elemente sortiert werden, indem sie mit einem Pivot verglichen werden.

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

• Der Algorithmus sortiert rekursiv das linke Subarray, das Elemente enth?lt, die kleiner als der Pivot sind.
• Die Rekursion stoppt, wenn das Subarray ein oder kein Element enth?lt, da es bereits sortiert ist.

Jetzt müssen wir den gleichen Vorgang auf der rechten Seite des Arrays durchführen:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

In diesem Beispiel ist die rechte Seite bereits sortiert, aber der Algorithmus wei? das nicht und sie w?re sortiert worden, wenn dies nicht der Fall gewesen w?re.

Das obige ist der detaillierte Inhalt vonErlernen des Schnellsortierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!