Wie funktioniert Javascript sort()?

Question

Wie sortiert der folgende Code dieses Array in numerischer Reihenfolge?

var array=[25, 8, 7, 41] 

array.sort(function(a,b) { 
    return a - b}) 

Ich weiß, dass, wenn das Ergebnis der Berechnung ist ...

Weniger als 0: "a" sortiert eine untere Index als "b" zu sein.
Null: "a" und "b" werden als gleich angesehen und es wird keine Sortierung durchgeführt.
Größer als 0: "b" ist nach einem niedrigeren Index als "a" sortiert.

Wird die Array-Sortierung Callback-Funktion oft im Laufe der Sortierung aufgerufen?

Wenn ja, würde ich gerne wissen, welche zwei Zahlen jedes Mal in die Funktion übergeben werden. Ich nahm an, es dauerte zuerst "25" (a) und "8" (b), gefolgt von "7" (a) und "41" (b), also:

25 (a) - 8 (b) = 17 (größer als Null, also sortiere "b" auf einen niedrigeren Index als "a"): 8, 25

7 (a) - 41 (b) = -34 (weniger als null, also sortiere " a b“ein niedriger Index als sein "?":! 7, 41

Wie die beiden Sätze von Zahlen werden dann in Beziehung zueinander sortiert

Bitte helfen Sie einen kämpfen Neuling

Answer 1

Wird die Array-Sortierung Callback-Funktion oft während der Sortierung aufgerufen?

Ja

Wenn ja, würde Ich mag wissen, welche zwei Zahlen in die Funktion jedes Mal übergeben werden

Sie Ihr selbst herausfinden konnte, mit:

array.sort((a,b) => { 
    console.log(`comparing ${a},${b}`); 
    return a > b ? 1 
       : a === b ? 0 
         : -1; 
}); 

E DIT

Dies ist die Ausgabe ich habe:

25,8 
25,7 
8,7 
25,41 

Answer 2

Ist die Arra y Callback-Funktion sortieren oft während der Sortierung aufgerufen?

Ja, das ist es genau. Der Callback wird verwendet, um Paare von Elementen im Array nach Bedarf zu vergleichen, um zu bestimmen, in welcher Reihenfolge sie sein sollten. Diese Implementierung der Vergleichsfunktion ist nicht atypisch, wenn es sich um eine numerische Sortierung handelt. Details in the spec oder some andere more readable Websites.

Answer 3

Der JavaScript-Interpreter hat eine Art sort algorithm Implementierung eingebaut. Sie ruft die Vergleichsfunktion einige Male während des Sortiervorgangs auf. Wie oft die Vergleichsfunktion aufgerufen wird, hängt vom jeweiligen Algorithmus, den zu sortierenden Daten und der Reihenfolge vor dem Sortieren ab.

Einige Sortieralgorithmen funktionieren schlecht auf bereits sortierten Listen, weil sie dadurch viel mehr Vergleiche machen als im typischen Fall. Andere kommen gut mit vorsortierten Listen zurecht, haben aber andere Fälle, in denen sie "ausgetrickst" werden können, um schlecht zu funktionieren.

Es gibt viele Sortieralgorithmen, die allgemein verwendet werden, weil kein einziger Algorithmus für alle Zwecke perfekt ist. Die zwei am häufigsten für die generische Sortierung verwendeten sind Quicksort und merge sort. Quicksort ist oft der schnellere der beiden, aber Merge Sort hat einige nette Eigenschaften, die es zu einer besseren Gesamtauswahl machen können. Merge sort ist stable, während Quicksort nicht ist. Beide Algorithmen sind parallelisierbar, aber die Art und Weise wie Merge Sort funktioniert, macht eine parallele Implementierung effizienter, wenn alle anderen gleich sind.

Ihr bestimmter JavaScript-Interpreter kann einen dieser Algorithmen oder etwas anderes vollständig verwenden. Der ECMAScript Standard does not specify which algorithm muss eine konforme Implementierung verwenden. Es leugnet sogar ausdrücklich das Bedürfnis nach Stabilität.

Answer 4

Paare von Werten verglichen werden, ein Paar zu einer Zeit. Die Paare, die verglichen werden, sind ein Implementierungsdetail - gehen Sie nicht davon aus, dass sie in jedem Browser gleich sind. Der Callback kann alles sein (also können Sie Strings oder römische Ziffern oder etwas anderes sortieren, wo Sie eine Funktion finden, die 1,0, -1 zurückgibt).

Eine Sache, die man bei JavaScript beachten sollte, ist, dass es nicht garantiert ist, dass es stabil ist.

Answer 5

Wird die Array-Sortierung Callback-Funktion oft im Laufe der Sortierung aufgerufen?

Da dies ein Vergleich sortieren, da N Artikel, sollte die Callback-Funktion im Durchschnitt (N * Lg N) mal für eine schnelle Art wie Quicksort aufgerufen werden. Wenn der verwendete Algorithmus etwa Bubble Sort ist, wird die Callback-Funktion im Durchschnitt (N * N) aufgerufen.

Die minimale Anzahl von Aufrufen für eine Vergleichssortierung ist (N-1) und das ist nur zum Erkennen einer bereits sortierten Liste (d. H. Früh in Bubble Sort, wenn keine Swaps auftreten).