Ausführliche Erklärung der Schnellsortierung in JavaScript

In diesem Artikel geht es um das schnelle Sortieren in JavaScript Wenn Sie sich mit dem schnellen Sortieren in JavaScript nicht auskennen, schauen wir uns diesen Artikel an Schneiden Sie den Unsinn ab und kommen Sie auf den Punkt

Schnelle Sortierung ist eine weitere typische Anwendung der Divide-and-Conquer-Idee in Sortieralgorithmen. Im Wesentlichen sollte die schnelle Sortierung als eine rekursive Divide-and-Conquer-Methode betrachtet werden, die auf der Blasensortierung basiert.

Der Name „Schnellsortierung“ ist einfach und grob, denn sobald Sie den Namen hören, werden Sie die Bedeutung seiner Existenz erkennen, die schnell und effizient ist. Es handelt sich um einen der schnellsten Sortieralgorithmen für die Verarbeitung! Big Data. Obwohl die Zeitkomplexität von Worst Case O(n²) erreicht hat, ist sie ausgezeichnet und schneidet in den meisten Fällen besser ab als der Sortieralgorithmus mit einer durchschnittlichen Zeitkomplexität von O(n log n). weiß es auch nicht. . . Glücklicherweise trat meine Zwangsstörung erneut auf, nachdem ich viele Informationen überprüft hatte, und fand schließlich eine zufriedenstellende Antwort beim „Algorithmus-Kunst- und Informatik-Wettbewerb“:

Die schlimmste Betriebssituation der schnellen Art ist O(n²). , wie zum Beispiel die schnelle Sortierung fortlaufender Nummern. Die amortisierte erwartete Zeit beträgt jedoch O(n log n), und der in der O(n log n)-Notation implizite konstante Faktor ist sehr klein, was viel kleiner ist als die Zusammenführungssortierung, deren Komplexität stabil und gleich O(n log) ist N). Daher ist für die meisten Zufallszahlenfolgen mit schwacher Ordnung die Schnellsortierung immer besser als die Zusammenführungssortierung.

Schnelle Sortieranimationsdemonstration

Schnelle Sortier-JavaScript-Code-Implementierung:

function quickSort(arr, left, right) {  
    var len = arr.length,  
        partitionIndex,  
        left = typeof left != 'number' ? 0 : left,  
        right = typeof right != 'number' ? len - 1 : right;  
  
    if (left < right) {  
        partitionIndex = partition(arr, left, right);  
        quickSort(arr, left, partitionIndex-1);  
        quickSort(arr, partitionIndex+1, right);  
    }  
    return arr;}function partition(arr, left ,right) {     //分区操作  
    var pivot = left,                      //设定基准值（pivot）  
        index = pivot + 1;  
    for (var i = index; i <= right; i++) {  
        if (arr[i] < arr[pivot]) {  
            swap(arr, i, index);  
            index++;  
        }          
    }  
    swap(arr, pivot, index - 1);  
    return index-1;}function swap(arr, i, j) {  
    var temp = arr[i];  
    arr[i] = arr[j];  
    arr[j] = temp;}

Das Obige ist der gesamte Inhalt dieses Artikels. Wenn Sie noch nicht viel darüber wissen, können Sie es leicht meistern, indem Sie mehr von beiden Seiten implementieren!

Verwandte Empfehlungen:

Detaillierte Erklärung der Js-Blasensortierung und Schnellsortierung

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung der Schnellsortierung in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!