Detaillierte Erläuterung des Javascript-Schnellsortierungsalgorithmus

Detaillierte Erläuterung des Javascript-Schnellsortierungsalgorithmus_Grundkenntnisse

WBOY

Freigeben： 2016-05-16 16:29:14

Original

1422 Leute haben es durchsucht

Schnellsortierung ist eine Verbesserung gegenüber der Blasensortierung. Teilen Sie die zu sortierenden Daten in zwei unabhängige Teile auf. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil. Verwenden Sie dann diese Methode, um die beiden Teile der Daten schnell zu sortieren Der Sortiervorgang kann rekursiv ablaufen und schließlich werden die gesamten Daten zu einer geordneten Sequenz.

Angenommen, das zu sortierende Array ist A[0]...A[N-1]. Wählen Sie zunächst zufällig einen Datenwert (normalerweise die erste Zahl des Arrays) als Benchmark-Daten und dann alle kleineren Zahlen aus als es ist. Setzen Sie es davor und alle Zahlen, die größer als es sind, werden dahinter platziert. Dieser Vorgang wird als One-Pass-Schnellsortierung bezeichnet. Es ist zu beachten, dass die schnelle Sortierung kein stabiler Sortieralgorithmus ist, d. h. die relativen Positionen mehrerer identischer Werte können sich am Ende des Algorithmus ändern.
Der Algorithmus der Schnellsortierung in einem Durchgang lautet:
1) Setzen Sie zwei Variablen auf niedrig und hoch. Wenn die Sortierung beginnt: niedrig=0, hoch=N-1; 2) Verwenden Sie das erste Array-Element als Referenzdaten und weisen Sie es der Basis zu, d. h. base=A[0]; 3) Von oben nach vorne suchen, also von hinten nach vorne suchen (hoch--), den ersten Wert A[hoch] finden, der kleiner als der Basiswert ist, und A[hoch] und A[niedrig] austauschen; 4) Suchen Sie von unten nach hinten, dh von vorne nach hinten (niedrig), finden Sie das erste A[niedrig], das größer als die Basis ist, und tauschen Sie A[niedrig] und A[hoch] aus 5) Wiederholen Sie die Schritte 3 und 4, bis niedrig=hoch;

Code kopieren

Der Code lautet wie folgt: Funktionspartition(Elemente, niedrig, hoch){ //Standardmäßig wird das erste Element links als Basiselement verwendet var base=elements[low];

while(low < high){

//Suche von hinten nach vorne, bis ein Element gefunden wird, das kleiner als das Basiselement ist, und tausche es aus
While(low < high && elements[high] >= base) high--;
var swap1=elements[low];elements[low]=elements[high];elements[high]=swap1;
//Suche von vorne nach hinten, bis ein Element gefunden wird, das größer als das Basiselement ist, und tausche es aus
while(low < high && elements[low] <= base) low ;
var swap2=elements[low];elements[low]=elements[high];elements[high]=swap2;
}
//Die Position des Referenzelements als Teilungsposition der Sequenz zurückgeben
Rückkehr niedrig;
}
Funktion sort(elements, low, high){
if(low // Teilen Sie die Sequenz in zwei Teile und teilen Sie sie in die Sequenz vor und nach der Teilungsposition auf. Die erstere Sequenz hat einen kleineren Wert als die Teilungsposition und die letztere Sequenz hat einen größeren Wert als die Teilungsposition
var partitionPos=partition(elements, low, high);
//Fortsetzen Sie die rekursive Sortierung der vorherigen Sequenz
Sortieren(Elemente, 0, PartitionPos-1);
//Sortieren Sie die nachfolgende Sequenz rekursiv weiter
Sort(elements, partitionPos 1, high);
}
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' elements);
sort(elemente, 0, elements.length-1);
console.log(' after: ' elements);

Effizienz:

Zeitkomplexität: Beste: O(nlog2n), Schlechteste: O(n^2), Durchschnitt: O(nlog2n). Raumkomplexität: O(nlog2n).

Stabilität: Instabil.