Algorithmus von JavaScript "sort()" Funktion

Question

Kürzlich, als ich mit JavaScript "sort()" -Funktion arbeitete, fand ich in einem der tutorials, dass diese Funktion die Zahlen nicht richtig sortiert. Statt Zahlen zu sortieren, muss eine Funktion hinzugefügt werden, die Zahlen vergleicht, wie dem folgenden Code: -

<script type="text/javascript"> 
function sortNumber(a,b) 
{ 
    return a - b; 
} 

var n = ["10", "5", "40", "25", "100", "1"]; 
document.write(n.sort(sortNumber)); 
</script> 

Der Ausgang dann kommt, wie: -

1,5,10,25,40,100 

Nun, was ich nicht verstehe ist, dass Warum ist das passiert & kann jemand bitte im Detail erzählen, welche Art von Algorithmus in dieser "sort()" Funktion verwendet wird? Das ist, weil ich für jede andere Sprache dieses Problem nicht gefunden habe, wo die Funktion die -Nummern nicht korrekt sortiert hat.

Jede Hilfe wird sehr geschätzt.

Answer 1

Nun, wenn Sie in der folgenden Liste sortieren, enthält es nur Strings:

var n = ["10", "5", "40", "25", "100", "1"]; 

So würde ich erwarten, jede Sprache sie als Strings vergleichen würde, also in einer Sortierreihenfolge resultierende:

var n = ["1", "10", "100", "25", "40", "5"]; 

Dies erfordert, dass Ihr Code eine benutzerdefinierte Sortierung verwendet (wie Sie getan haben), um die Zeichenfolgen für Sortierzwecke in Ganzzahlen zurück zu konvertieren.

bearbeiten

Als Zipfel, die JavaScript sort() method Sorten von Standard erwähnte alphabetisch Elemente, einschließlich Zahlen:

standardmäßig sortiert der sort() -Methode die Elemente alphabetisch und aufsteigend. Zahlen werden jedoch nicht korrekt sortiert (40 kommt vor 5). Um Zahlen zu sortieren, müssen Sie eine Funktion hinzufügen, die Zahlen vergleicht.

Einfach erstaunlich ... so ist eine benutzerdefinierte Sortierung auch für eine ganze Reihe von Ganzzahlen erforderlich.

Answer 2

Und was, wenn Ihr n ist definiert als:

var n = [10, 5, 40, 25, 100, 1]; 

Answer 3

Das Problem bei der Verwendung von Zeichenketten liegt Zahlen darzustellen, die die Sortierfunktion leider als Standard der Fall ist. Strings sind alphabetisch sortiert. Die Vergleichsfunktion in Ihrem Code erzwingt nur, dass die Strings als Zahlen ausgewertet werden.

Ich würde es für sehr schlecht API-Design, dass die Sortierfunktion standardmäßig auf die Elemente als Strings zu behandeln, aber es kann angegeben JavaScript lose Art System ..

Answer 4

Javascripts Art sortiert standardmäßig lexikographischer, alphabetisch erforderlich sein. So wie ich es verstehe, wird jedes Element als eine Saite behandelt. Der interne Sortieralgorithmus ist höchstwahrscheinlich Quicksort oder Mergesort. Um in der Lage zu sein, Quicksort zu verwenden, müssen Sie in der Lage sein, Elemente miteinander in Beziehung zu setzen, ist es größer als b? Im Stringfall ist diese Reihenfolge bereits implementiert.

Da möchten Sie möglicherweise Ihre benutzerdefinierten Datentypen usw. sortierenSie können eine Funktion zur Verfügung stellen, die definiert, wie zwei Elemente angeordnet werden.

Von Ihrem Beispiel bestimmt Ihre Funktion die Reihenfolge von zwei Zahlen a und b. Javascript-Sortierung verwendet dann Ihre Funktion, um zu sortieren, wie die Elemente sortiert werden.

Es stellte sich heraus, dass mergesort von Mozilla verwendet wird, sehen Sie: Javascript Array.sort implementation?

Answer 5

Die Funktion sort wird das Array in einer alphabetical sort order sortieren, auch wenn es von ganzen Zahlen besteht; Das ist der Grund, warum Ihr Array so sortiert ist, indem Sie sort ohne Parameter aufrufen.

sortOrder ist eine Vergleichsfunktion, die verwendet wird, um eine neue Sortierreihenfolge für das Array zu definieren; Diese Funktion wird

• 0 zurückkehren, wenn a und b den gleichen Wert sind
• einen Wert > 0, wenn a einen größeren Wert als b
• ein Wert < 0 hat, wenn a einen kleineren Wert hat als b

In JavaScript wird "1" - "2"-1 zurückkehren , das ist eine Zahl und keine Zeichenfolge mehr; unter Verwendung der Vergleichsfunktion sortOrder auf dem Array aus Zahlen in Strings gewickelten, sind Bestellung Sie das Array in einer numerischen Sortierreihenfolge, was somit in 1,5,10,25,40,100, und nicht in 1,10,100,25,40,5

Answer 6

Sie können die Sortierung delegieren zu Ihrer eigenen Sortierfunktion:

function sortnum(a,b) { 
return parseInt(a,10)-parseInt(b,10); 
} 
var n = ["10", "5", "40", "25", "100", "1"]; 
alert(n.sort(sortnum)); //=>["1", "5", "10", "25", "40", "100"] 

Answer 7

Um Ihre Frage zu beantworten, wie die Sortierfunktion funktioniert, werde ich es im Detail erklären. Wie in den meisten Antworten hier gesagt wurde, wird das Aufrufen von nur sort() für ein Array Ihr Array mit Strings sortieren. Konvertiere deine Integer auch in Strings. Blech!

Wenn Sie Ihre Artikel als Zeichen statt als Zahlen betrachten, macht es Sinn, dass sie so sortiert werden. Eine gute Möglichkeit, dies zu sehen, besteht darin, Ihren Zahlen Buchstaben zuzuordnen.

//0 = a 
//1 = b 
//2 = c 
//4 = e 
//5 = f 
//These two arrays are treated the same because they're composed of strings. 
var nums = ["10", "5", "40", "25", "100", "1"]; 
var chars = ["ba", "f", "ea", "cf", "baa", "b"]; 

//Here we can see that sort() correctly sorted these strings. Looking at the 
//alphabetical characters we see that they are in the correct order. Looking 
//at our numbers in the same light, it makes sense that they are sorted 
//this way as well. After all, we did pass them as strings to our array. 
chars.sort(); //["b", "ba", "baa", "cf", "ea", "f"] 
nums.sort(); //["1", "10", "100", "25", "40", "5"] 

//The bad part of sort() comes in when our array is actually made up of numbers. 
var nums = [10, 5, 40, 25, 100, 1]; 
nums.sort(); //[1, 10, 100, 25, 40, 5] 

//As a result of the default sorting function converting numbers to strings 
//before sorting, we get an unwanted result. We can fix this by passing in our 
//own function as a parameter to sort(). 

können Sie steuern, wie das Array zu sortieren, indem Sie Ihre eigene Funktion als Parameter an die Funktion übergeben sort(). Das ist nett, aber wenn Sie nicht wissen, wie die sort() Funktion funktioniert, wird es Ihnen wirklich nicht gut tun.

sort() ruft Ihre Funktion mehrmals auf, um das Array neu anzuordnen. Abhängig davon, was von Ihrer Funktion zurückgegeben wird, teilt sort() mit, was mit den Elementen im Array zu tun ist. Wenn eine negative Zahl oder 0 zurückgegeben wird, findet keine Neuanordnung statt. Wenn eine positive Zahl zurückgegeben wird, wechseln die beiden Elemente. sort() merkt sich, welche Nummern es bereits getestet hat, so dass es nicht zu einem späteren Zeitpunkt erneut Tests von Nummern gibt, nachdem es die Elemente umgeschalten hat. Wenn sort() Elemente neu anordnet, verschiebt es sich um eine Position zurück und prüft, ob diese beiden Elemente bereits getestet wurden. Wenn es nicht ist, wird es sie testen. Wenn dies der Fall ist, wird es fortgesetzt, ohne dass Ihre Funktion auf ihnen ausgeführt wird.

Sortierung Zahlen

Nehmen wir ein einfaches Beispiel nehmen, und ich werde Sie durch sie gehen:

var arr = [50, 90, 1, 10, 2]; 

arr = arr.sort(function(current, next){ 
    //My comments get generated from here 
    return current - next; 
}); 

//1 : current = 50, next = 90 
// : current - next (50 - 90 = -40) 
// : Negative number means no re-arranging 
// : Array now looks like [50, 90, 1, 10, 2] 
// 
//2 : current = 90, next = 1 
// : current - next (90 - 1 = 89) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [50, 1, 90, 10, 2] 
// 
//If sort() didn't backtrack, the next check would be 90 and 10, switch those 
//positions, check 90 and 2, and switch again. Making the final array 
//[50, 1, 10, 2, 90], not sorted. But lucky for us, sort() does backtrack. 
// 
//3 : current = 50, next = 1 
// : current - next (50 - 1 = 49) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 50, 90, 10, 2] 
// 
//If sort() wasn't smart, it would now check 50 and 90 again. What a waste! 
//But lucky for us again, sort() is smart and knows it already made this 
//check and will continue on. 
// 
//4 : current = 90, next = 10 
// : current - next (90 - 10 = 80) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 50, 10, 90, 2] 
// 
//sort() backtracks one position and sees that it has not checked 50 and 10 
// 
//5 : current = 50, next = 10 
// : current - next (50 - 10 = 40) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 10, 50, 90, 2] 
// 
//sort() backtracks one position and sees that it has not checked 1 and 10 
// 
//6 : current = 1, next = 10 
// : current - next (1 - 10 = -9) 
// : Negative number means no re-arranging 
// : Array now looks like [1, 10, 50, 90, 2] 
// 
//sort() remembers that it already checked 10 and 50 so it skips ahead 
//sort() remembers that it already checked 50 and 90 so it skips ahead 
// 
//7 : current = 90, next = 2 
// : current - next (90 - 2 = 88) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 10, 50, 2, 90] 
// 
//sort() backtracks one position and sees that it has not checked 50 and 2 
// 
//8 : current = 50, next = 2 
// : current - next (50 - 2 = 48) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 10, 2, 50, 90] 
// 
//sort() backtracks one position and sees that it has not checked 10 and 2 
// 
//9 : current = 10, next = 2 
// : current - next (10 - 2 = 8) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [1, 2, 10, 50, 90] 
// 
//sort() backtracks one position and sees that it has not checked 1 and 2 
// 
//10: current = 1, next = 2 
// : current - next (1 - 2 = -1) 
// : Negative number means no re-arranging 
// : Array now looks like [1, 2, 10, 50, 90] 
// 
//sort() remembers that it already checked 2 and 10 so it skips ahead 
//sort() remembers that it already checked 10 and 50 so it skips ahead 
//sort() remembers that it already checked 50 and 90 so it skips ahead 
//sort() has no more items to check so it returns the final array 
//which is [1, 2, 10, 50, 90] 

Wenn Sie das Array wollte [90, 50, 10, 2, 1] in absteigender Reihenfolge zu bestellen Sie können einfach die Return-Anweisung ändern aus so return current - next; zu return next - current; wie:

var arr = [50, 90, 1, 10, 2]; 

arr = arr.sort(function(current, next){ 
    //My comments get generated from here 
    return next - current; 
}); 

//1 : current = 50, next = 90 
// : next - current (90 - 50 = 40) 
// : Positive number means sort() will switch these positions in the array 
// : Array now looks like [90, 50, 1, 10, 2] 
// 
//2 : current = 50, next = 1 
// : next - current (1 - 50 = -49) 
// : Negative number means no re-arranging 
// : Array now looks like [90, 50, 1, 10, 2] 
// 
//etc. 

Es spielt keine Rolle, wenn Ihr Array COMPO sed von "string numbers" "5" oder nur Zahlen 5 bei Verwendung einer eigenen Funktion zum Sortieren von Zahlen. Denn wenn JavaScript Mathematik macht, behandelt es "String-Nummern" als Zahlen. das heißt "5" - "3" = 2

Sortierung Strings

Wenn Sie Strings sortieren, können Sie sie vergleichen die > und < (Größer-als und weniger als) Operatoren. Der Größer-als-Operator sortiert die Zeichenfolge in aufsteigender Reihenfolge (A-Z, 1-9), und der Kleiner-als-Operator sortiert nach absteigender Reihenfolge (Z-A, 9-1). Verschiedene Browser verwenden unterschiedliche Sortieralgorithmen. Wenn Sie also nach Zeichenfolgen sortieren, müssen Sie sicherstellen, dass Sie entweder 1 oder -1, nicht wahr oder falsch, zurückgeben.

Zum Beispiel funktioniert dies in Chrome und FF, aber nicht IE:

var arr = ['banana', 'orange', 'apple', 'grape']; 

arr = arr.sort(function(current, next){ 
    return current > next; 
}); 

Die Art und Weise Ihr Sortieralgorithmus in jedem Browser funktioniert, um sicherzustellen, den ternären Operator verwenden.

var arr = ['banana', 'orange', 'apple', 'grape']; 

arr = arr.sort(function(current, next){ 
    return current > next? 1: -1; 
}); 

Wenn die Art und Weise ändern, die Sie (nach aufsteigend oder absteigend), zusätzlich zu Änderung der Operatoren zu sortier, können Sie den gleichen Betreiber halten und schalten die current und next Variablen wie wir, wenn Zahlen zu sortieren. Oder, da wir den ternären Operator verwenden, könnten Sie die 1 und -1 wechseln.

Sortieren von Objekten

Hier ist ein netter Trick, dass ich dachte, ich würde hier hinzufügen in. Sie können Objekte sortieren, wenn Sie sie zu einem Array hinzufügen und deren Schlüssel zum Vergleichen verwenden. Hier ist ein Beispiel.

var arr = [ 
    {id: 2, name: 'Paul'}, 
    {id: 1, name: 'Pete'} 
]; 

//sort numerically 
arr = arr.sort(function(current, next){ 
    return current.id - next.id; 
}); 
//Array now looks like [{id: 1, name: 'Pete'}, {id: 2, name: 'Paul'}] 

//sort alphabetically 
arr = arr.sort(function(current, next){ 
    return current.name > next.name? 1: -1; 
}); 
//Array now looks like [{id: 2, name: 'Paul'}, {id: 1, name: 'Pete'}] 

Rekapitulation

Zahlen
in aufsteigender Reihenfolge (1, 2, 3 ...) sortieren: function(a, b){return a - b;}
in absteigender Reihenfolge (9, 8, 7 .. .): function(a, b){return b - a;}

Saiten
sortierenin aufsteigende Reihenfolge (A, B, C ...): function(a, b){return a > b? 1: -1;}
in absteigend (Z, Y, X ...)): function(a, b){return b > a? 1: -1;}

Objekte sortieren sie zu einem Array hinzuzufügen,
dann sortiert nach key: function(a, b){return a.key - b.key;}