TL;DR

Zawsze z powodzeniem sortowałem moje tablice w ten sposób

> [1,1,0,2].sort(function(a, b){ return a>b })
Array [0, 1, 2, 1]
// in Opera 12. Results may vary between sorting algorithm implementations

Dlaczego?

Ponieważ funkcja porównawcza zwraca false (lub 0, równoważnie) nawet wtedy, gdy b jest większa niż a. Ale 0 implikuje, że dwa elementy są uważane za równe-i algorytm sortowania uważa, że.

In-Depth Wyjaśnienie

Funkcje porównawcze w JavaScript

Jak działają funkcje porównawcze?

The Array::sort metoda może przyjmować opcjonalną, niestandardową funkcję porównawczą jako swój argument. Funkcja ta przyjmuje dwa argumenty (powszechnie określane jako a i b), które powinna porównać i ma zwracać liczbę

• > 0 Gdy a jest uważane za większe niż b i należy je posortować po it
• == 0 gdy a jest uważane za równe b i nie ma znaczenia, który będzie pierwszy
• < 0 gdy a jest uważany za mniejszy niż b i powinien być sortowany przed

Jeśli nie zwróci liczby, wynik zostanie oddany do liczby (co jest przydatne dla booleanów). Zwracana liczba nie musi być dokładnie -1 lub 0 lub 1 (choć zazwyczaj tak jest).

Konsekwentne porządkowanie

Aby być konsekwentnym, funkcja porównania musiałaby spełnić równanie

comp(a, b) == -1 * comp(b, a)
// or, if values other than -1, 0 and 1 are considered:
comp(a, b) * comp(b, a) <= 0

Jeśli ten wymóg jest złamany, sortowanie będzie zachowywać się niezdefiniowany.

Powołując się na ES5. 1 spec na sort (to samo w ES6 spec):

jeśli comparefn jest [ ... ] nie jest spójną funkcją porównawczą dla elementów tej tablicy, zachowanie sort jest zdefiniowane w implementacji.

funkcja {[27] } jest spójną funkcją porównawczą dla zbioru of values S if all of the requirements below are specified for all values a, b, i c (ewentualnie ta sama wartość) w zbiorze S: zapis a <CF b oznacza comparefn(a,b) < 0; a =CF b oznacza comparefn(a,b) = 0 (jednego ze znaków); oraz a >CF b oznacza comparefn(a,b) > 0.

wywołanie comparefn(a,b) zawsze zwraca tę samą wartość v, gdy podano określoną parę wartości a i b jako dwa argumenty. Ponadto Type(v) jest liczbą, a v nie jest NaN. Zauważ, że oznacza to, że dokładnie jeden z a <CF b, a =CF b, i {[38] } będzie prawdziwe dla danej pary a i b.

• wywołanie comparefn(a,b) nie modyfikuje tego obiektu.
• a =CF a (refleksyjność)
• If a =CF b, then b =CF a (symetria)
• If a =CF b and b =CF c, then a =CF c (przechodniość z =CF)
• If a <CF b and b <CF c, then a <CF c (przechodniość <CF)
• If a >CF b and b >CF c, then a >CF c (przechodniość >CF)

uwaga: powyższe warunki są konieczne i wystarczające do zapewnienia, że comparefn dzieli zbiór S na klasy równoważności i że te klasy równoważności są całkowicie uporządkowane.

Co to znaczy? Co mnie to obchodzi?

Algorytm sortowania musi porównywać elementy tablicy z każdym inne. Aby wykonać dobrą i wydajną pracę, nie musi porównywać każdego przedmiotu z każdym innym, ale musi być w stanie rozumować o ich zamówieniu. Aby to dobrze działało, istnieje kilka zasad, których musi przestrzegać funkcja porównywania niestandardowego. Trywialne jest to, że element a jest równy sobie (compare(a, a) == 0) - to pierwszy element z powyższej listy (refleksywność). Tak, to trochę matematyczne, ale dobrze się opłaca.

Najważniejszą z nich jest przechodniość. Mówi, że gdy algorytm porównał dwie wartości a i b, a także b z c i odkrył, stosując funkcję porównawczą, która np. a = b i b < c, to może oczekiwać, że a < c również się trzyma. Wydaje się to tylko logiczne i jest wymagane dla dobrze zdefiniowanego, spójnego uporządkowania.

Ale twoja funkcja porównawcza zawodzi . Spójrzmy na ten przykład:

 function compare(a, b) { return Number(a > b); }
 compare(0, 2) == 0 // ah, 2 and 0 are equal
 compare(1, 0) == 1 // ah, 1 is larger than 0
 // let's conclude: 1 is also larger than 2

Ooops. I dlatego algorytm sortowania może zawieść (w specyfikacji jest to be "zachowanie zależne od implementacji " -tj. nieprzewidywalne wyniki), gdy jest wywoływane z funkcją porównawczą, która nie jest spójna.

Dlaczego złe rozwiązanie jest tak powszechne?

Ponieważ w wielu innych językach istnieją algorytmy sortowania, które nie oczekują trójstronnego porównania , a jedynie boolean mniejszy od operatora. C++ std::sort jest tego dobrym przykładem. Zostanie po prostu zastosowany dwa razy z wymienionymi argumentami jeśli zachodzi potrzeba ustalenia równości. Co prawda, może to być bardziej wydajne i mniej podatne na błędy, ale wymaga więcej wywołań do funkcji porównawczej, jeśli operator nie może być inlinowany.

Kontrwywiad

Przetestowałem swoją funkcję porównawczą i działa!

Tylko przez szczęście, jeśli spróbujesz jakiegoś przypadkowego przykładu. Lub dlatego, że twój zestaw testów jest wadliwy - niepoprawny i / lub niekompletny.

Oto mały skrypt, który znalazłem powyższy minimalny kontrprzykład:

function perms(n, i, arr, cb) {
// calls callback with all possible arrays of length n
    if (i >= n) return cb(arr);
    for (var j=0; j<n; j++) {
        arr[i] = j;
        perms(n, i+1, arr, cb);
    }
}
for (var i=2; ; i++) // infinite loop
    perms(i, 0, [], function(a) {
        if (    a.slice().sort(function(a,b){ return a>b }).toString()
             != a.slice().sort(function(a,b){ return a-b }).toString() )
            // you can also console.log() all of them, but remove the loop!
            throw a.toString();
    });

Jaka funkcja porównawcza jest poprawna?

Nie używaj żadnej funkcji porównawczej, jeśli chcesz sortować leksykograficznie. W razie potrzeby pozycje w tablicy będą stringified.

Ogólna funkcja porównawcza, która działa jak operatory relacyjne, może być zaimplementowana jako

function(a, b) {
    if (a > b) return 1;
    if (a < b) return -1;
    /* else */ return 0;
}

Za pomocą kilku sztuczek można to minifigurować do odpowiednika function(a,b){return +(a>b)||-(a<b)}.

Dla liczb , można po prostu zwrócić ich różnica, która przestrzega wszystkich powyższych praw:

function(a, b) {
    return a - b; // but make sure only numbers are passed (to avoid NaN)
}

Jeśli chcesz sortować w odwrotnej kolejności, po prostu weź odpowiedni i zamień a na b.

Jeśli chcesz sortować typy złożone (obiekty itp.), zamień każdy a i każdy b na dostęp do danych właściwości, wywołanie metody lub cokolwiek chcesz sortować według.