2 Beispiele für den Javascript-Sortieralgorithmus Merge Sort (Merge Sort)_Grundkenntnisse

Merge Sort ist ein effektiver Sortieralgorithmus, der auf Merge-Operationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode (Divide and Conquer).

Die Sortiermethode zum Zusammenführen besteht darin, zwei (oder mehr) geordnete Listen zu einer neuen geordneten Liste zusammenzuführen, dh die zu sortierende Sequenz wird in mehrere Teilsequenzen unterteilt und jede Teilsequenz wird geordnet. Fügen Sie dann die geordneten Teilsequenzen zur geordneten Gesamtsequenz zusammen.

Merge Sort ist ein effektiver Sortieralgorithmus, der auf Merge-Operationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode (Divide and Conquer). Führen Sie die bereits geordneten Teilsequenzen zusammen, um eine vollständig geordnete Sequenz zu erhalten. Ordnen Sie also zuerst jede Teilsequenz und dann die Teilsequenzsegmente. Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, spricht man von einer 2-Wege-Zusammenführung.

Der Vorgang des Zusammenführungsvorgangs ist wie folgt:

1. Beantragen Sie Platz, sodass seine Größe der Summe der beiden sortierten Sequenzen entspricht. Dieser Platz wird zum Speichern der zusammengeführten Sequenz verwendet.
2. Setzen Sie zwei Zeiger, deren Anfangspositionen die beiden sortierten Sequenzen sind. Startposition
3. Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie ein relativ kleines Element aus, platzieren Sie es im Zusammenführungsbereich und bewegen Sie den Zeiger zur nächsten Position
4. Wiederholen Sie Schritt 3, bis ein bestimmter Zeiger erreicht ist erreicht das Ende der Sequenz
5. Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz

Beispiel 1:

Code kopieren Der Code lautet wie folgt:

/**
* Der Zusammenführungsvorgang (Merge), auch Zusammenführungsalgorithmus genannt, bezieht sich auf den Vorgang des Zusammenführens zweier sortierter Sequenzen zu einer Sequenz.
* Der Zusammenführungssortierungsalgorithmus basiert auf Zusammenführungsoperationen.
*
* Der Vorgang des Zusammenführens ist wie folgt:
*
* 1. Beantragen Sie Speicherplatz, sodass seine Größe der Summe zweier sortierter Sequenzen entspricht. Dieser Speicherplatz wird zum Speichern der zusammengeführten Sequenzen verwendet Sequenz
* 2. Setzen Sie zwei Zeiger, die Anfangspositionen sind die Startpositionen der beiden sortierten Sequenzen
* 3. Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie das relativ kleine Element aus und fügen Sie es in die Zusammenführung ein Leertaste und Bewegen Sie den Zeiger zur nächsten Position
* 4. Wiederholen Sie Schritt 3, bis ein Zeiger das Ende der Sequenz erreicht
* 5. Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz
*
*/

Funktion mergeSort(items) {
if (items.length < 2) {
return items;
}

var middle = Math.floor(items.length / 2) ,
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));

params.unshift(0, items.length);
items.splice.apply(items, params);

return items;

function merge(left, right ) {
var result = [],
il = 0,
ir = 0;

while (il < left.length && ir < right.length) {
if ( left[il] < right[ir]) {
                            result.push(left[il]); >                                                                                                                         return result.concat(left.slice(il)) .concat(right.slice(ir) ); = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];

mergeSort(arr);



Beispiel 2:





Code kopieren

Der Code lautet wie folgt: