compareFnOptional

Eine Funktion, die die Reihenfolge der Elemente bestimmt. Die Funktion wird mit den folgenden Argumenten aufgerufen:

a

Das erste Element zum Vergleich. Wird niemalsundefined sein.

b

Das zweite Element zum Vergleich. Wird niemalsundefined sein.

Die Funktion sollte eine Zahl zurückgeben, bei der:

• Ein negativer Wert anzeigt, dassa vorb kommt.
• Ein positiver Wert anzeigt, dassa nachb kommt.
• Null oderNaN anzeigt, dassa undb als gleich betrachtet werden.

Um sich das zu merken, bedenken Sie, dass(a, b) => a - b Zahlen in aufsteigender Reihenfolge sortiert.

Wenn die Funktion nicht angegeben wird, werden die Array-Elemente in Strings umgewandelt und dann gemäß dem Unicode-Codepunktwert jedes Zeichens sortiert.

Die Referenz auf das Original-Array, das nun sortiert ist. Beachten Sie, dass das Arrayin place sortiert wird und keine Kopie erstellt wird.

WenncompareFn nicht angegeben wird, werden alle nicht-undefined-Array-Elemente durch Umwandeln in Strings sortiert und die Strings gemäß der Reihenfolge ihrer UTF-16-Codes verglichen. Zum Beispiel kommt "banana" vor "cherry". In einer numerischen Sortierung kommt 9 vor 80, aber da Zahlen in Strings umgewandelt werden, kommt "80" im Unicode vor "9". Alleundefined-Elemente werden ans Ende des Arrays sortiert.

Diesort() Methode bewahrt leere Plätze. Wenn das Quell-Arraysparse ist, werden die leeren Plätze an das Ende des Arrays verschoben und kommen immer nach allenundefined.

WenncompareFn angegeben ist, werden alle nicht-undefined-Array-Elemente gemäß dem Rückgabewert der Vergleichsfunktion sortiert (alleundefined-Elemente werden ans Ende des Arrays sortiert, ohne Aufruf dercompareFn).

Daher hat die Vergleichsfunktion die folgende Form:

function compareFn(a, b) {  if (a is less than b by some ordering criterion) {    return -1;  } else if (a is greater than b by the ordering criterion) {    return 1;  }  // a must be equal to b  return 0;}

Formal erwartet man, dass der Komparator die folgenden Eigenschaften aufweist, um ein korrektes Sortierverhalten sicherzustellen:

• Rein: Der Komparator verändert die zu vergleichenden Objekte oder irgendeinen äußeren Zustand nicht. (Dies ist wichtig, weil es keine Garantie gibt,wann undwie der Komparator aufgerufen wird, so dass ein bestimmter Anruf keine sichtbaren Effekte nach außen haben sollte.)
• Stabil: Der Komparator gibt bei denselben Eingabepaaren dasselbe Ergebnis zurück.
• Reflexiv:compareFn(a, a) === 0.
• Anti-symmetrisch:compareFn(a, b) undcompareFn(b, a) müssen beide0 sein oder entgegengesetzte Vorzeichen haben.
• Transitiv: WenncompareFn(a, b) undcompareFn(b, c) beide positiv, null oder negativ sind, dann hatcompareFn(a, c) dieselbe Positivität wie die vorherigen beiden.

Ein Komparator, der den oben genannten Beschränkungen entspricht, kann immer alle von1,0 und-1 zurückgeben oder konsequent0 zurückgeben. Wenn ein Komparator beispielsweise nur1 und0 oder nur0 und-1 zurückgibt, wird er nicht zuverlässig sortieren können, da dieAnti-Symmetrie gebrochen ist. Ein Komparator, der stets0 zurückgibt, wird das Array gar nicht verändern, ist aber dennoch zuverlässig.

Der standardmäßig lexikographische Komparator erfüllt alle oben genannten Bedingungen.

Um Zahlen anstelle von Strings zu vergleichen, kann die Vergleichsfunktionb vona subtrahieren. Die folgende Funktion sortiert das Array in aufsteigender Reihenfolge (wenn es nichtNaN enthält):

function compareNumbers(a, b) {  return a - b;}

Diesort() Methode istgenerisch. Sie erwartet lediglich, dass derthis-Wert einelength-Eigenschaft und Integer-Index-Properties hat. Obwohl Strings auch array-ähnlich sind, ist diese Methode nicht geeignet, auf sie angewendet zu werden, da Strings unveränderlich sind.

Das folgende Beispiel erstellt vier Arrays und zeigt das Original-Array, dann die sortierten Arrays. Die numerischen Arrays werden ohne eine Vergleichsfunktion sortiert und dann unter Verwendung einer.

const stringArray = ["Blue", "Humpback", "Beluga"];const numberArray = [40, 1, 5, 200];const numericStringArray = ["80", "9", "700"];const mixedNumericArray = ["80", "9", "700", 40, 1, 5, 200];function compareNumbers(a, b) {  return a - b;}stringArray.join(); // 'Blue,Humpback,Beluga'stringArray.sort(); // ['Beluga', 'Blue', 'Humpback']numberArray.join(); // '40,1,5,200'numberArray.sort(); // [1, 200, 40, 5]numberArray.sort(compareNumbers); // [1, 5, 40, 200]numericStringArray.join(); // '80,9,700'numericStringArray.sort(); // ['700', '80', '9']numericStringArray.sort(compareNumbers); // ['9', '80', '700']mixedNumericArray.join(); // '80,9,700,40,1,5,200'mixedNumericArray.sort(); // [1, 200, 40, 5, '700', '80', '9']mixedNumericArray.sort(compareNumbers); // [1, 5, '9', 40, '80', 200, '700']

Arrays von Objekten können sortiert werden, indem man den Wert einer ihrer Eigenschaften vergleicht.

const items = [  { name: "Edward", value: 21 },  { name: "Sharpe", value: 37 },  { name: "And", value: 45 },  { name: "The", value: -12 },  { name: "Magnetic", value: 13 },  { name: "Zeros", value: 37 },];// sort by valueitems.sort((a, b) => a.value - b.value);// sort by nameitems.sort((a, b) => {  const nameA = a.name.toUpperCase(); // ignore upper and lowercase  const nameB = b.name.toUpperCase(); // ignore upper and lowercase  if (nameA < nameB) {    return -1;  }  if (nameA > nameB) {    return 1;  }  // names must be equal  return 0;});

Für das Sortieren von Strings mit nicht-ASCII-Zeichen, d.h. Zeichenketten mit Akzenten (e, é, è, a, ä, etc.), Strings aus anderen als der englischen Sprache, verwenden SieString.prototype.localeCompare(). Diese Funktion kann diese Zeichen vergleichen, so dass sie in der richtigen Reihenfolge erscheinen.

const items = ["réservé", "premier", "communiqué", "café", "adieu", "éclair"];items.sort((a, b) => a.localeCompare(b));// items is ['adieu', 'café', 'communiqué', 'éclair', 'premier', 'réservé']

DercompareFn kann innerhalb des Arrays mehrfach pro Element aufgerufen werden. Abhängig von der Natur descompareFn kann dies zu einem hohen Overhead führen. Je mehr Arbeit eincompareFn leistet und je mehr Elemente es zu sortieren gibt, desto effizienter kann es sein,map() für die Sortierung zu verwenden. Die Idee ist, das Array einmal zu durchlaufen, um die tatsächlich für das Sortieren verwendeten Werte in ein temporäres Array zu extrahieren, das temporäre Array zu sortieren und dann das temporäre Array zu durchlaufen, um die richtige Ordnung zu erreichen.

// the array to be sortedconst data = ["delta", "alpha", "charlie", "bravo"];// temporary array holds objects with position and sort-valueconst mapped = data.map((v, i) => ({ i, value: someSlowOperation(v) }));// sorting the mapped array containing the reduced valuesmapped.sort((a, b) => {  if (a.value > b.value) {    return 1;  }  if (a.value < b.value) {    return -1;  }  return 0;});const result = mapped.map((v) => data[v.i]);

Es gibt eine Open-Source-Bibliothek namensmapsort, die diesen Ansatz verfolgt.

Diesort() Methode gibt eine Referenz auf das Original-Array zurück. Das bedeutet, dass das Mutieren des zurückgegebenen Arrays auch das Original-Array ändern wird.

const numbers = [3, 1, 4, 1, 5];const sorted = numbers.sort((a, b) => a - b);// numbers and sorted are both [1, 1, 3, 4, 5]sorted[0] = 10;console.log(numbers[0]); // 10

Falls Siesort() verwenden möchten, ohne das Original-Array zu verändern, aber einflach kopiertes Array erhalten möchten, wie dies bei anderen Array-Methoden (z.B.map()) der Fall ist, verwenden Sie dietoSorted() Methode. Alternativ können Sie eine flache Kopie vor dem Aufruf vonsort() machen, indem Sie dieSpread-Syntax oderArray.from() verwenden.

const numbers = [3, 1, 4, 1, 5];// [...numbers] creates a shallow copy, so sort() does not mutate the originalconst sorted = [...numbers].sort((a, b) => a - b);sorted[0] = 10;console.log(numbers[0]); // 3

Seit Version 10 (oder ECMAScript 2019) schreibt die Spezifikation vor, dassArray.prototype.sort stabil ist.

Angenommen, Sie haben eine Liste von Studenten zusammen mit ihren Noten. Beachten Sie, dass die Liste der Studenten bereits alphabetisch nach Namen vorsortiert ist:

const students = [  { name: "Alex", grade: 15 },  { name: "Devlin", grade: 15 },  { name: "Eagle", grade: 13 },  { name: "Sam", grade: 14 },];

Nachdem Sie dieses Array nachgrade in aufsteigender Reihenfolge sortiert haben:

students.sort((firstItem, secondItem) => firstItem.grade - secondItem.grade);

Hat die Variablestudents dann den folgenden Wert:

[  { name: "Eagle", grade: 13 },  { name: "Sam", grade: 14 },  { name: "Alex", grade: 15 }, // original maintained for similar grade (stable sorting)  { name: "Devlin", grade: 15 }, // original maintained for similar grade (stable sorting)];

Es ist wichtig zu beachten, dass Studenten, die die gleiche Note haben (zum Beispiel Alex und Devlin), in der gleichen Reihenfolge bleiben, wie vor dem Aufruf vonsort(). Das garantiert ein stabiles Sortierverfahren.

Vor Version 10 (oder ECMAScript 2019) war die Sortierstabilität nicht garantiert, was dazu führen konnte, dass das Ergebnis folgendes war:

[  { name: "Eagle", grade: 13 },  { name: "Sam", grade: 14 },  { name: "Devlin", grade: 15 }, // original order not maintained  { name: "Alex", grade: 15 }, // original order not maintained];

Wenn eine Vergleichsfunktion nicht alle Regeln der Reinheit, Stabilität, Reflexivität, Anti-Symmetrie und Transitivität erfüllt, wie in derBeschreibung erklärt, ist das Verhalten des Programms nicht wohldefiniert.

Betrachten Sie zum Beispiel diesen Code:

const arr = [3, 1, 4, 1, 5, 9];const compareFn = (a, b) => (a > b ? 1 : 0);arr.sort(compareFn);

DiecompareFn Funktion hier ist nicht wohldefiniert, da sie die Anti-Symmetrie nicht erfüllt: Wenna > b, gibt sie1 zurück; aber indem mana undb austauscht, gibt sie0 anstelle eines negativen Werts zurück. Deshalb wird das resultierende Array in verschiedenen Engines unterschiedlich sein. Zum Beispiel würde V8 (verwendet von Chrome, Node.js, etc.) und JavaScriptCore (verwendet von Safari) das Array überhaupt nicht sortieren und[3, 1, 4, 1, 5, 9] zurückgeben, während SpiderMonkey (verwendet von Firefox) das Array aufsteigend sortieren würde, als[1, 1, 3, 4, 5, 9].

Wird jedoch diecompareFn Funktion geringfügig geändert, so dass sie-1 oder0 zurückgibt:

const arr = [3, 1, 4, 1, 5, 9];const compareFn = (a, b) => (a > b ? -1 : 0);arr.sort(compareFn);

Dann sortieren V8 und JavaScriptCore es absteigend, als[9, 5, 4, 3, 1, 1], während SpiderMonkey es unverändert zurückgibt:[3, 1, 4, 1, 5, 9].

Aufgrund dieser Implementierungskonsistenz wird immer empfohlen, Ihren Komparator wohldefiniert zu machen, indem Sie den fünf Bedingungen folgen.

Leere Plätze werden an das Ende des Arrays verschoben.

console.log(["a", "c", , "b"].sort()); // ['a', 'b', 'c', empty]console.log([, undefined, "a", "b"].sort()); // ["a", "b", undefined, empty]

Diesort() Methode liest dielength Eigenschaft vonthis. Dann sammelt sie alle vorhandenen, ganzzahlig indizierten Eigenschaften im Bereich von0 bislength - 1, sortiert sie und schreibt sie zurück. Wenn es in diesem Bereich fehlende Eigenschaften gibt, werden die entsprechenden nachfolgenden Eigenschaftengelöscht, als ob die nicht vorhandenen Eigenschaften am Ende sortiert würden.

const arrayLike = {  length: 3,  unrelated: "foo",  0: 5,  2: 4,};console.log(Array.prototype.sort.call(arrayLike));// { '0': 4, '1': 5, length: 3, unrelated: 'foo' }

• Polyfill vonArray.prototype.sort mit modernem Verhalten wie stabile Sortierung incore-js
• Indizierte Sammlungen Leitfaden
• Array
• Array.prototype.reverse()
• Array.prototype.toSorted()
• String.prototype.localeCompare()
• TypedArray.prototype.sort()
• Elemente in V8 sortieren auf v8.dev (2018)
• StabileArray.prototype.sort auf v8.dev (2019)
• Array.prototype.sort Stabilität von Mathias Bynens