Zusammenfassung von sieben in JavaScript implementierten Sortieralgorithmen (empfohlen!)

Vorwort

Der sogenannte Sortieralgorithmus dient dazu, eine oder mehrere Datengruppen anhand bestimmter Algorithmusfaktoren nach einem vorgegebenen Muster neu zu sortieren. Diese neue Sequenz folgt bestimmten Regeln und spiegelt gewisse Gesetzmäßigkeiten wider. Daher lassen sich die verarbeiteten Daten leicht prüfen und berechnen, was die Rechenleistung erheblich verbessert. Für die Sortierung fordern wir zunächst eine gewisse Stabilität, das heißt, wenn zwei identische Elemente gleichzeitig in einer Sequenz auftreten, ändern sich nach einem bestimmten Sortieralgorithmus die relativen Positionen der beiden vor und nach der Sortierung nicht. Mit anderen Worten: Auch wenn zwei Elemente exakt gleich sind, werden sie beim Sortiervorgang unterschieden und es kommt nicht zu Verwechslungen.

Blasensortierung

Bubblesort ist ein Algorithmus für Einsteiger, es gibt aber auch einige interessante Möglichkeiten, damit zu experimentieren. Im Allgemeinen gibt es drei Möglichkeiten, Bubblesort zu schreiben:

Vergleichen und tauschen Sie jeweils zwei auf einmal, wobei der Maximal-/Minimalwert bis zur letzten Ziffer aufgerundet wird.
Optimierte Schreibmethode: Verwenden Sie eine Variable, um aufzuzeichnen, ob in der aktuellen Vergleichsrunde ein Austausch stattgefunden hat. Wenn kein Austausch stattgefunden hat, bedeutet dies, dass die Reihenfolge bereits in Ordnung ist und keine weitere Sortierung erfolgt.

Grundlegender Algorithmus

Die räumliche Komplexität beträgt O(1) und die zeitliche Komplexität beträgt O(n2).

const sort = (arr) => {
    für (sei i = 0, len = arr.length; i < len-1; i++){
        für (sei j = 0; j < len-1-i; j++) {
            wenn (arr[j] > arr[j+1]) {
                arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    Rückflug an
}

Nach jeder Runde der äußersten For-Schleife wird der Maximalwert der verbleibenden Zahlen auf die letzte Ziffer der aktuellen Runde verschoben, und einige benachbarte Zahlen werden in der Mitte ausgetauscht, um eine geordnete Ordnung zu schaffen. Die Gesamtzahl der Vergleiche beträgt (n-1)+(n-2)+(n-3)+…+1(n−1)+(n−2)+(n−3)+…+1.

Die zweite Schreibweise basiert auf dem Basisalgorithmus:

const sort = (arr) => {
    für (sei i = 0, len = arr.length; i < len - 1; i++) {
        let isSwap = false
        für (sei j = 0; j < len - 1 - i; j++) {
            wenn (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                isSwap = wahr
            }
        }
        wenn (!istSwap) {
            brechen;
        }
    }
    Rückflug an;
};

Die räumliche Komplexität beträgt O(1); die zeitliche Komplexität beträgt O(n2) – vorzugsweise O(n);

Bei jedem Durchlauf der äußersten For-Schleife durch eine Runde wird der Maximalwert der verbleibenden Zahlen trotzdem an die letzte Ziffer der aktuellen Runde verschoben. Der Vorteil dieser Methode gegenüber der ersten besteht darin, dass, wenn in einer Vergleichsrunde kein Austausch stattfindet, die Sortierung sofort abgebrochen wird, da die verbleibenden Zahlen zu diesem Zeitpunkt in der richtigen Reihenfolge sein müssen.

Auswahl Sortieren

Die Idee der Auswahlsortierung besteht darin, das Array in einer Doppelschleife zu durchlaufen, nach jeder Vergleichsrunde den Index des kleinsten Elements zu finden und ihn an die erste Stelle zu setzen.

Grundlegender Algorithmus

const sort = (arr) => {
    für (sei i = 0, len = arr.length; i < len - 1; i++) {
        sei minIndex = i
        für (sei j = i+1; j < len; j++) {
            wenn (arr[i] > arr[j]) {
                minIndex = j
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    Rückflug an;
};

Binäre Auswahlsortierung - Optimierung

Der Auswahlsortierungsalgorithmus kann ebenfalls optimiert werden. Da in jeder Durchlaufrunde der Minimalwert gefunden wird, warum sollte nicht auch der Maximalwert gefunden werden? Dies ist die Idee der binären Auswahlsortierung.

Durch die Verwendung der binären Auswahlsortierung und die Aufzeichnung der Minimal- und Maximalwerte in jeder Auswahlrunde kann der Bereich des zu durchlaufenden Arrays um die Hälfte reduziert werden.

const sort = (arr) => {
    für (sei i = 0, len = arr.length; i < len / 2; i++) {
        sei minIndex = i;
        sei maxIndex = i;
        für (sei j = i + 1; j < len-i; j++) {
            wenn (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
            wenn (arr[maxIndex] < arr[j]) {
                maxIndex = j;
            }
        }
        wenn (minIndex === maxIndex) unterbrechen;
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        wenn (maxIndex === i) {
            maxIndex = minIndex;
        }
        const lastIndex = Länge - i - 1;
        [arr[maxIndex], arr[letzterIndex]] = [arr[letzterIndex], arr[maxIndex]];
    }
    Rückflug an; 
};

Einfügungssortierung

Die Idee des Insertionsort ist sehr einfach. Es gibt ein sehr häufiges Szenario im Leben: Beim Pokern sortieren wir die Karten, während wir sie ziehen. Jedes Mal, wenn wir eine Karte ziehen, fügen wir sie an der entsprechenden Stelle in die vorhandenen Karten auf unserer Hand ein und schließen so nach und nach die gesamte Sortierung ab.

Es gibt zwei Möglichkeiten, Insertionsort zu schreiben:

• Austauschmethode: Beim Einfügen neuer Zahlen diese immer wieder mit den vorherigen Zahlen vertauschen, bis sie die passende Position finden.
• Verschiebemethode: Während des Einfügens einer neuen Nummer wird diese ständig mit der vorherigen Nummer verglichen und die vorherige Nummer wird ständig nach hinten verschoben. Wenn die neue Nummer ihre Position gefunden hat, kann sie einmal eingefügt werden.
  

Einfügungssortierung durch Vertauschen

const sort = (arr) => {
    für (sei i = 1, len = arr.length; i < len; i++) {
        sei j = i;
        während (j >= 1 und arr[j] < arr[j - 1]) {
            arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            J--
        }
    }
    Rückflug an;
};

Wenn es weniger als zwei Zahlen gibt, gibt es kein Sortierproblem und natürlich ist keine Einfügung erforderlich, sodass wir direkt ab der zweiten Zahl einfügen.

Mobile Methode

Wir haben festgestellt, dass bei der Insertionsort-Methode mit der Austauschmethode die Zahlen jedes Mal ausgetauscht werden müssen. In der Realität passt die neu eingefügte Zahl aber nicht unbedingt an die Position der Zahl, mit der sie vertauscht wird. Das heißt, es wurde nur kurz an die neue Position verschoben und wird nach dem nächsten Vergleich, wenn es erneut ausgetauscht werden muss, sofort an die Position der vorherigen Nummer verschoben.

Daraus lässt sich eine Optimierungslösung ableiten: Man vergleiche zunächst die neu eingefügte Zahl und schiebe die davor liegenden, größeren Zahlen immer weiter nach hinten, bis eine passende Stelle für die neue Zahl gefunden und dann eingefügt ist.

In dieser Lösung müssen wir die neu eingefügten Zahlen vorübergehend speichern. Der Code lautet wie folgt:

const sort = (arr) => {
    für (sei i = 1, len = arr.length; i < len; i++) {
        sei j = i-1;
        sei cur = arr[i];
        während (j >= 0 und aktuell < arr[j]) {
            arr[j+1] = arr[j]
            J--;
        }
        arr[j+1] = aktuell
    }
    Rückflug an;
};

Muschelsortierung

Im Juli 1959 veröffentlichte Donald Shell, ein Doktor der Mathematik von der Universität Cincinnati, den Shell-Sortieralgorithmus in Communications of the ACM, der zu den ersten Algorithmen gehörte, der die Zeitkomplexität auf unter O(n2) reduzierte. Obwohl die schlechteste Zeitkomplexität der ursprünglichen Shell-Sortierung immer noch O(n2) beträgt, kann die optimierte Shell-Sortierung O(n1,3) oder sogar O(n7/6) erreichen.

Shellsort ist im Wesentlichen eine Optimierung von Insertionsort. Es nutzt die Einfachheit von Insertionsort und überwindet den Nachteil von Insertionsort, dass immer nur zwei benachbarte Elemente gleichzeitig ausgetauscht werden. Die Grundidee ist:

• Das zu sortierende Array wird entsprechend einem bestimmten Intervall in mehrere Unterarrays unterteilt, und jede Gruppe wird separat eingefügt und sortiert. Hier bedeutet Gruppieren nach Intervall nicht, ein kontinuierliches Array zu verwenden, sondern einen Wert in einem bestimmten Intervall zu verwenden, um eine Gruppe zu bilden.
• Reduzieren Sie das Intervall für die nächste Sortierrunde schrittweise
• In der letzten Runde wird das Intervall auf 11 gesetzt, was der direkten Verwendung des Insertionsort entspricht. Aber nach der vorherigen „Makrosteuerung“ ist das Array grundsätzlich geordnet, sodass die Einfügesortierung zu diesem Zeitpunkt nur noch eine kleine Menge an Austausch benötigt, um abgeschlossen zu werden. Beispielsweise ist der Prozess der Shell-Sortierung des Arrays [8, 3, 34, 6, 4, 1, 44, 45, 43, 2, 23] wie folgt:
  

Erster Durchgang (5-Intervallsortierung): Teilen Sie das Subarray entsprechend dem Intervall 5 in fünf Gruppen auf, nämlich [8, 1, 23], [3, 44], [34, 45], [6, 43], [4, 2]. Fügen Sie sie in sortierter Reihenfolge ein. Nach dem Sortieren werden sie zu: [1, 8, 23], [3, 44], [34, 45], [6, 43], [2, 4]. Das gesamte Array wird zu [1, 3, 34, 6, 2, 8, 44, 45, 43, 4, 23].

Zweiter Durchgang (2-Intervallsortierung): Teilen Sie das Subarray gemäß Intervall 2 in zwei Gruppen auf, nämlich [1, 34, 2, 44, 43, 23], [3, 6, 8, 45, 4]. Sortieren Sie sie durch Einfügen, und nach dem Sortieren werden sie zu: [1, 2, 23, 34, 43, 44], [3, 4, 6, 8, 45], und das gesamte Array wird zu [1, 3, 2, 4, 23, 6, 34, 8, 43, 45, 44]. Hier gibt es eine sehr wichtige Eigenschaft: Nachdem wir die 2-Intervall-Sortierung abgeschlossen haben, bleibt das Array immer noch in der 5-Intervall-Reihenfolge. Mit anderen Worten: Das Sortieren mit kleineren Intervallen verschlechtert das Ergebnis des vorherigen Schritts nicht.

Der dritte Durchgang (11-Intervallsortierung, entspricht der direkten Einfügungssortierung): Teilen Sie das Teilarray gemäß Intervall 1 in eine Gruppe auf, die das gesamte Array darstellt. Führen Sie eine Insertionsortierung durch. Nach den ersten beiden Sortierungen ist das Array im Wesentlichen in Ordnung, sodass dieser Schritt nur ein wenig Auslagerung erfordert, um die Sortierung abzuschließen. Nach dem Sortieren wird das Array zu [1, 2, 3, 4, 6, 8, 23, 34, 43, 44, 45] und das Sortieren ist abgeschlossen.

const sort = arr => {
    const len ​​= arr.länge;
    wenn (Länge < 2) {
        Rückflug an;
    }
    lass Lücke = Math.floor(Länge / 2);
    während (Lücke > 0) {
        für (sei i = Lücke; i < Länge; i++) {
            sei j = i;
            sei cur = arr[i];
            während (j >= 0 und aktuell < arr[j - Lücke]) {
                arr[j] = arr[j - Lücke];
                j -= Lücke;
            }
            arr[j] = aktuell;
        }
        Lücke = Math.floor(Lücke / 2);
    }
    Rückflug an;
}

Heapsortierung

Der Heapsort-Prozess läuft wie folgt ab:

1. Verwenden Sie die Sequenz, um einen großen oberen Heap zu erstellen, nehmen Sie die Nummer oben aus dem Heap heraus (legen Sie sie an das Ende des zu sortierenden Arrays).
2. Passen Sie die restlichen Zahlen an, bilden Sie einen neuen großen Stapel und nehmen Sie die oberste Zahl erneut vom Stapel.
3. Wiederholen Sie den Vorgang immer wieder, um den gesamten Sortiervorgang abzuschließen.
   

Funktion sortieren(arr) {
    für (lass i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.Länge)
    }
    für (sei j = arr.length - 1; j > 0; j--) {
        [arr[0], arr[j]] = [arr[j], arr[0]]
        Heap anpassen(arr, 0, j)
    }
}

Funktion adjustHeap(arr, i, Länge) {
    sei tmp = arr[i]
    für (sei k = i * 2 + 1; k < Länge; k = k * 2 + 1) {
        wenn (k + 1 < Länge und arr[k] < arr[k + 1]) {
            k++;
        }
        wenn (arr[k] > tmp) {
            arr[i] = arr[k];
            ich = k;
        } anders {
            brechen;
        }
        arr[i] = tmp;
    }
}

Schnelle Sortierung

Der Quicksort-Algorithmus wurde 1960 von CAR Hoare vorgeschlagen. Seine Zeitkomplexität beträgt ebenfalls O(nlogn), aber im Vergleich zu den verschiedenen Sortieralgorithmen mit einer Zeitkomplexität von O(nlogn) ist es in den meisten Fällen effizienter, sodass Quicksort häufig verwendet wird. Darüber hinaus ist die von Quicksort übernommene Teile-und-herrsche-Idee sehr praktisch, was Quicksort bei Interviewern sehr beliebt macht. Daher ist es besonders wichtig, die Idee von Quicksort zu beherrschen.

Die Grundidee des Quicksort-Algorithmus ist:

1. Nehmen Sie eine Zahl aus dem Array, den sogenannten Pivot
2. Durchlaufen Sie das Array, platzieren Sie die Zahlen, die größer als die Kardinalität sind, rechts davon und die Zahlen, die kleiner als die Kardinalität sind, links davon. Nach Abschluss der Durchquerung wird das Array in zwei Bereiche unterteilt: links und rechts
3. Behandeln Sie den linken und rechten Bereich als zwei Arrays und wiederholen Sie die ersten beiden Schritte, bis die Sortierung abgeschlossen ist.
4. Tatsächlich wird bei jeder Durchquerung der Quicksortierung die Kardinalität an die Endposition gebracht. In der ersten Durchlaufrunde wird 1 Kardinalität aussortiert, in der zweiten Durchlaufrunde werden 2 Kardinalitäten aussortiert (eine Kardinalität für jeden Bereich, aber wenn ein Bereich leer ist, kann in dieser Runde nur eine Kardinalität aussortiert werden), in der dritten Durchlaufrunde werden 4 Kardinalitäten aussortiert (ebenso kann im schlimmsten Fall nur eine Kardinalität aussortiert werden) und so weiter. Die Gesamtzahl der Durchläufe beträgt logn~n-mal und die Zeitkomplexität jeder Durchlaufrunde beträgt O(n). Daher lässt sich leicht analysieren, dass die Zeitkomplexität der Schnellsortierung O(nlogn)~O(n2) und die durchschnittliche Zeitkomplexität O(nlogn) beträgt.

const partition = (arr, start, end) => {
    let pivot = arr[start]; // Nimm die erste Zahl als Basis let left = start + 1; // Beginne mit der Partitionierung ab der zweiten Zahl let right = end; // Rechte Grenze // Verlasse die Schleife, wenn sich links und rechts treffen while (left < right) {
        // Finde die erste Position, die größer ist als die Kardinalität while (left < right && arr[left] <= pivot) left++;
        // Vertausche diese beiden Zahlen, sodass die linke Partition kleiner oder gleich der Kardinalität ist und die rechte Partition größer oder gleich der Kardinalität ist, wenn (links != rechts) {
            [arr[links], arr[rechts]] = [arr[rechts], arr[links]];
            Rechts--;
        }
    }
    // Wenn links und rechts gleich sind, vergleiche arr[right] und pivot separat
    wenn (links == rechts && arr[rechts] > pivot) rechts--;
    // Basis und Mitte vertauschen if (right != start) [arr[left], pivot] = [pivot, arr[left]];
    //Gibt den Index des mittleren Wertes zurück return right;
}

const quickSort = (arr, start, end) => {
    wenn (Start >= Ende) zurückgeben;
    const Mitte = Partition (arr, Start, Ende)
    quickSort(arr, start, middle - 1);
    quickSort(arr, Mitte + 1, Ende);
}

const sort = arr => {
    quickSort(arr, 0, arr.Länge -1);
}

Zusammenführendes Sortieren

Mergesort ist ein effektiver Sortieralgorithmus, der auf der Merge-Operation basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Teile-und-herrsche-Methode. Führen Sie die geordneten Teilfolgen zusammen, um eine vollständig geordnete Folge zu erhalten. Ordnen Sie also zuerst jede Teilfolge und dann die Teilfolgensegmente. Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, nennt man das eine 2-Wege-Zusammenführung.

Beschreibung des Algorithmus

• Teilen Sie die Eingabesequenz der Länge n in zwei Teilsequenzen der Länge n/2 auf.
• Auf diese beiden Teilsequenzen wird jeweils Mergesort angewendet.
• Füge zwei sortierte Teilsequenzen zu einer endgültigen sortierten Sequenz zusammen.
  

const merge = (links, rechts) => {
    lass Ergebnis = [];
    während (linke.Länge > 0 und rechte.Länge > 0) {
        wenn (links[0] <= rechts[0]) {
            Ergebnis.push(links.Shift());
        } anders {
            Ergebnis.push(rechts.shift());
        }
    }
    während (links.Länge) Ergebnis.Push(links.Shift());
    während (rechts.Länge) Ergebnis.Push(rechts.Shift());
    Ergebnis zurückgeben;
}

const sort = (arr) => {
    sei len = arr.length;
    wenn (Länge < 2) {
        Rückflug an;
    }
    const middle = Math.floor(länge / 2),
        links = arr.slice(0, Mitte),
        rechts = arr.slice(Mitte);
    return merge(sortieren(links), sortieren(rechts));
};

Zusammenfassen

Damit ist dieser Artikel über sieben in JavaScript implementierte Sortieralgorithmen abgeschlossen. Weitere relevante Inhalte zu JavaScript-Sortieralgorithmen finden Sie in den vorherigen Artikeln von 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!