Einführung in die Zusammenführungssortierung in JavaScript (Codebeispiel)

Dieser Artikel bietet Ihnen eine Einführung in die Zusammenführungssortierung in JavaScript (Codebeispiele). Ich hoffe, dass er Ihnen als Referenz dienen wird.

Zusammenführungssortierung (MERGE-SORT) ist ein effektiver Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Der Algorithmus verwendet die Divide-and-Conquer-Methode (pide andConquer) ist eine sehr typische Anwendung. 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 bidirektionalen Zusammenführung.

Zusammenführungssortierung

Zusammenführungssortierung ist eine sehr stabile Sortiermethode und ihre zeitliche Komplexität beträgt NlogN in Bezug auf Durchschnitt, Beste und Schlechteste.

Zwei Schritte der Zusammenführungssortierung

1. Zuerst teilen, bis nur noch eine Zahl vorhanden ist

2. Teilung abgeschlossen. Danach beginnen die rekursive Zusammenführung

Split-Prozess

Wie Sie in der obigen Abbildung sehen können, führen Sie die Zusammenführungssortierung An durch Das Array wird in zwei Teile geteilt und die Teilung wird beendet, wenn nur eine Zahl vorhanden ist.
Dann ist der Aufteilungscode sehr einfach, nämlich einen Zeiger q zu erhalten, der auf die Mitte zeigt, und das Array in zwei Teile aufzuteilen: (Start, p) und (p, Ende).

• p stellt den Anfangsindex des Arrays dar

• r stellt den Endindex des Arrays dar

    function pide(p, r){
        return Math.floor( (p + r) / 2 );
    }

Der Zusammenführungsprozess

Der Zusammenführungsprozess ist wie im Bild oben gezeigt

1. Traverse zwei Datensätze

2. Vergleichen Sie die Größen

3. Der kleinere Wert wird herausgenommen und an die erste Position gesetzt

Zum Beispiel:

• Angenommen, die aktuellen Daten von Array A sind [2,5,1,3]

• Nachher unsere Aufteilung wird (0,2),(2,4);

• Wir erhalten zwei durch A.slice(0,2) und A.slice(2,4) => Arrays A1[2,5] und A2[1,3]

• Dann durchlaufen wir das Array [2,5,1,3] und zum ersten Mal wird den Vergleich beider Seiten erhalten. Die kleine Zahl ist 1, das zweite Mal ist 2, das dritte Mal ist 3 und das vierte Mal ist 5

    function merge(A, p, q, r){
        const A1 = A.slice(p, q);
        const A2 = A.slice(q, r);
        
        // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值
        
        A1.push(Number.MAX_SAFE_INTEGER);
        A2.push(Number.MAX_SAFE_INTEGER);
        // 循环做比较，每次取出较小的那个值
        for (let i = p, j = 0, k = 0; i <h3 id="Hauptprogramm">Hauptprogramm</h3><p>Das Hauptprogramm besteht darin, die obige Operation rekursiv zu wiederholen </p><pre class="brush:php;toolbar:false">    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = pide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

Vollständiger Code

    function pide(p, r) {
      return Math.floor((p + r) / 2);
    }
    
    function merge(A, p, q, r) {
      const A1 = A.slice(p, q);
      const A2 = A.slice(q, r);
      A1.push(Number.MAX_SAFE_INTEGER);
      A2.push(Number.MAX_SAFE_INTEGER);
    
      for (let i = p, j = 0, k = 0; i <p class="comments-box-content"></p>

Das obige ist der detaillierte Inhalt vonEinführung in die Zusammenführungssortierung in JavaScript (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!