Algoritmo di JavaScript "sort()" Funzione

Question

Recentemente quando lavoravo con la funzione JavaScript "sort()", ho trovato in uno dei tutorials che questa funzione non ordina correttamente i numeri. Invece di ordinare i numeri, una funzione deve essere aggiunto che mette a confronto i numeri, come il seguente codice: -

<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> 

L'uscita quindi si presenta come: -

1,5,10,25,40,100 

Ora quello che non ho capito è che perché questo si verifica & qualcuno può dirlo in dettaglio su quale tipo di algoritmo viene utilizzato in questa funzione "sort()"? Questo perché per qualsiasi altra lingua, non ho trovato questo problema in cui la funzione non ha ordinato correttamente i numeri .

Qualsiasi aiuto è molto apprezzato.

Answer 1

Beh, se si ordina il seguente elenco, che contiene solo le stringhe:

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

Quindi mi aspetterei qualsiasi lingua li paragonerei come stringhe, con il risultato di un ordinamento di:

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

Che richiede che il codice utilizzi un ordinamento personalizzato (come è stato fatto) per restituire le stringhe ai numeri interi ai fini dell'ordinamento.

Modifica

Come accennato appuntita, per default il genere elementi JavaScript sort() method alfabetico, compresi i numeri:

Per default, il metodo sort() ordina gli elementi alfabeticamente e ascendente. Tuttavia, i numeri non verranno ordinati correttamente (40 viene prima di 5). Per ordinare i numeri, è necessario aggiungere una funzione che confronta i numeri.

Semplicemente fantastico ... quindi è richiesto un ordinamento personalizzato anche per un array di numeri interi.

Answer 2

E cosa succede se il n è definito come:

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

Answer 3

Il problema è con l'uso di stringhe per rappresentare i numeri, che la funzione di ordinamento fa purtroppo come predefinito. Le stringhe sono ordinate alfabeticamente. La funzione di confronto nel codice costringe semplicemente le stringhe a essere valutate come numeri.

lo considererei molto cattivo design API che le impostazioni predefinite della funzione di ordinamento per trattare gli elementi come stringhe, ma può essere necessario dato sistema di tipo sciolto di JavaScript ..

Answer 4

JavaScript sorta sort by lessicografico impostazione predefinita, alfabetico. Quindi, a quanto ho capito, ogni elemento è trattato come una stringa. L'algoritmo di ordinamento interno è molto probabilmente quicksort o mergesort. Per essere in grado di usare quicksort è necessario essere in grado di mettere in relazione gli elementi tra loro, è più grande di b? Nel caso delle stringhe questo ordine è già implementato.

Poiché è possibile ordinare i tipi di dati personalizzati, ecc.puoi fornire una definizione funzionale su come ordinare due elementi.

Dal tuo esempio la tua funzione determina l'ordine di due numeri a e b. L'ordinamento Javascript utilizza quindi la funzione che indica come ordinare gli elementi.

scopre che Mergesort è utilizzato da Mozilla, guarda: Javascript Array.sort implementation?

Answer 5

La funzione sort ordinerà l'array in un alphabetical sort order, anche se si tratta di numeri interi; questo è il motivo per cui la matrice è ordinata in questo modo chiamando sort senza un parametro.

sortOrder è una funzione di confronto che viene utilizzata per definire un nuovo ordinamento per l'array; questa funzione restituisce

• 0, se a e b sono dello stesso valore
• un valore > 0, se a ha un valore più grande di b
• un valore < 0, se a ha un valore minore di b

In JavaScript, "1" - "2" tornerà -1 , che è un numero e non una stringa più; utilizzando la funzione di confronto sortOrder sul vostro array composto da numeri avvolti in stringhe, si sta ordinando la matrice in una numerico ordine sorta, con conseguente 1,5,10,25,40,100, e non in 1,10,100,25,40,5

Answer 6

È possibile delegare l'ordinamento per la tua funzione di ordinamento:

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

Per rispondere alla tua domanda su come funziona la funzione di ordinamento, la spiegherò in dettaglio. Come è stato detto nella maggior parte delle risposte, chiamare solo sort() su un array ordinerà l'array usando le stringhe. Converti anche i tuoi numeri interi in stringhe. Blech!

Se pensi ai tuoi articoli come caratteri anziché numeri, è logico che vengano ordinati in questo modo. Un buon modo per vedere questo è di assegnare lettere ai tuoi numeri.

//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(). 

È possibile controllare come ordinare la matrice passando la propria funzione come parametro alla funzione sort(). Questo è bello, ma a meno che tu non sappia come funziona la funzione sort(), in realtà non ti servirà a nulla.

sort() chiamerà la funzione più volte per riorganizzare l'array. A seconda di ciò che viene restituito dalla funzione dice a sort() cosa fare con gli elementi nella matrice. Se viene restituito un numero negativo o 0, non avviene alcuna riorganizzazione. Se viene restituito un numero positivo, i due elementi cambiano posizione. sort() tiene traccia di quali numeri ha già testato, quindi non finisce di testare i numeri più tardi dopo aver cambiato gli articoli. Se sort() riordina gli elementi, si tornerà indietro di una posizione e vedrà se ha già provato prima questi due elementi. Se non lo ha, li metterà alla prova. Se lo ha, continuerà senza eseguire la funzione su di loro.

Numbers Ordinamento

Facciamo un semplice esempio e io vi guiderà attraverso di essa:

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] 

Se si voleva la matrice per essere ordinati in ordine [90, 50, 10, 2, 1] decrescente si può semplicemente modificare l'istruzione di ritorno da return current - next; a return next - current; in questo modo:

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. 

non importa se la matrice è compo sed di "string numeri" "5" o solo numeri 5 quando si utilizza la propria funzione per ordinare i numeri. Perché quando JavaScript sta facendo matematica, tratta i "numeri di stringa" come numeri. vale a dire "5" - "3" = 2

ordinamento delle stringhe

Quando si ordina le stringhe, è possibile confrontarli con gli operatori > e < (più grandi di e meno-che). L'operatore maggiore di ordina la stringa in ordine ascendente (A-Z, 1-9) e l'operatore minore di ordina in ordine decrescente (Z-A, 9-1). Browser diversi utilizzano algoritmi di ordinamento diversi, quindi quando si ordina per stringhe è necessario assicurarsi di restituire 1 o -1, non vero o falso.

Ad esempio, questo funziona in Chrome e FF, ma non IE:

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

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

Il modo per assicurarsi che il proprio algoritmo di ordinamento funziona in tutti i browser, utilizzare l'operatore ternario.

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

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

Quando si cambia il modo in cui stai ordinamento (crescente o decrescente), oltre a cambiare gli operatori, è possibile mantenere lo stesso operatore e passare le variabili current e next come abbiamo fatto durante l'ordinamento numeri. Oppure, poiché stiamo utilizzando l'operatore ternario, è possibile passare a 1 e -1.

Ordinamento oggetti

Ecco un trucco che ho pensato che vorrei aggiungere qui. È possibile ordinare gli oggetti se li si aggiunge a un array e utilizzare la chiave per confrontare. Ecco un esempio.

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'}] 

Riassunto

Per ordinare numeri
in ordine crescente (1, 2, 3 ...): function(a, b){return a - b;}
in cassa (9, 8, 7 decrescente .. .): function(a, b){return b - a;}

Per ordinare stringhe
in ordine crescente (A, B, C ...): function(a, b){return a > b? 1: -1;}
in ordine discendente (Z, Y, X ...): function(a, b){return b > a? 1: -1;}

Per ordinare oggetti li aggiungere ad un array,
quindi ordinare per chiave: function(a, b){return a.key - b.key;}