Kann eine instabile JavaScript-Sortierung stabil werden?

Stabiles Sortieren in JavaScript mit einem Twist

Das Sortieren einer Sammlung von Objekten ist eine häufige Aufgabe in der Programmierung, die oft Stabilität erfordert, um das Original zu bewahren Reihenfolge gleicher Elemente. Dem verwendeten Sortieralgorithmus ist jedoch möglicherweise keine Stabilität inhärent.

Einführung einer stabilen, nicht stabilen Sortierung

Ein überraschender, aber effektiver Ansatz besteht darin, eine instabile Sortierung umzuwandeln Funktion in eine stabile Funktion umwandeln. Vor dem Sortieren werden die Positionen aller Elemente ermittelt. Die Sortierbedingung wird geändert, um sowohl den Primärschlüssel als auch die ursprüngliche Position des Elements als Sekundärschlüssel zu berücksichtigen.

Durch die Verwendung der Position als Tiebreaker im Vergleich wird die Stabilität des endgültigen Sortierergebnisses sichergestellt.

Implementierung in JavaScript

Der folgende Codeausschnitt stellt eine Beispielimplementierung in JavaScript dar:

<code class="javascript">function stableSort(array, key) {
  const positions = [];

  for (let i = 0; i < array.length; i++) {
    positions[i] = i;
  }

  array.sort((a, b) => {
    const keyComparison = a[key].localeCompare(b[key]);
    return keyComparison || positions[a] - positions[b];
  });
}</code>

In diesem Code sortiert die Funktion „stableSort“ das Array nach dem angegebenen Wert Schlüssel auf stabile Weise. Das Positions-Array erfasst die Anfangspositionen der Elemente. Die Sortierbedingung basiert auf „localeCompare“ für Zeichenfolgenvergleiche und greift als Tiebreaker auf den Positionsvergleich zurück.

Dieser Ansatz bietet die Flexibilität, jeden instabilen Sortieralgorithmus zu nutzen und gleichzeitig die Stabilität für gleiche Elemente aufrechtzuerhalten.

Das obige ist der detaillierte Inhalt vonKann eine instabile JavaScript-Sortierung stabil werden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!