Sortieralgorithmus – Sortierung zusammenführen [mit Code]

Was ist Zusammenführungssortierung?

Einfach ausgedrückt besteht die Zusammenführungssortierung darin, zwei geordnete Sequenzen zusammenzufügen.

Empfohlenes Tutorial: PHP-Video-Tutorial

So kombinieren Sie zwei geordnete Sequenzen Was ist mit sie zusammen integrieren?

Dann nehmen wir an, dass es M=｛m1,m2,m3,....,mx｝ Sequenzen und N =｛n1,n2,n3,.... gibt, ny} Sequenz, diese beiden Sequenzen sind bereits geordnete Sequenzen K = {}, vergleichen Sie dann m1 und n1, fügen Sie m1 < n1 hinzu und fügen Sie dann m1 in die K-Sequenz ein Das heißt, m2 und n1 werden das nächste Mal verglichen, bis alle Vergleiche abgeschlossen und in Reihenfolge K gefüllt sind.

Da die Zusammenführungssortierung geordnete Sequenzen integriert, bedeutet das nicht, dass ungeordnete Sequenzen nicht sortiert werden können?

Die Zusammenführungssortierung basiert auf der Divide-and-Conquer-Methode, das heißt, eine völlig ungeordnete Sequenz kann drahtlos geteilt werden, um eine geordnete Sequenz zu erhalten , m2, m3, ...., mx}, die M-Sequenz ist eine völlig ungeordnete Sequenz, dann kann die M-Sequenz in mehrere kleine Sequenzen unterteilt werden - {m1, m2}, {m3, m4 }....{ mx-1, mx}; Zu diesem Zeitpunkt sind diese Sequenzen in Ordnung, dann können sie durch die Zusammenführungsoperation sortiert werden, sodass die Zusammenführungssortierung auch ungeordnete Sequenzen sortieren kann und ihre Geschwindigkeit nach der schnellen Sortierung, die zu Stable gehört, an zweiter Stelle steht Sortierung.

Wie teile ich eine Sequenz auf?

Wie in der vorherigen Frage erwähnt, basiert die Zusammenführungssortierung auf „Teilen und Erobern“, und „Teilen und Erobern“ spiegelt sich in der Teilungssequenz wider. Zum Beispiel: Jetzt gibt es M ={m1, m2, m3, ...., mx}, die erste Division: M1 = {m1, m2, ..., m(x+1)/2}, M2 = {m(x+1 )/2 +1 , m(x+1)/2 +2,...,mx}, nach der ersten Division werden die M1- und M2-Sequenzen erhalten, dann werden M1 und M2 geteilt und nach mehreren Divisionen ist x/2 Erhalten Sie + x% 2 Sequenzen und führen Sie sie dann einzeln zusammen.

Die spezifischen Schritte dieses Algorithmus:

1. Geben Sie die ersten Zeiger links und in der Mitte an (linke Punkte zeigen auf das erste Element von Sequenz 1). , rechts zeigt auf Sequenz 2 (das erste Element)

2. Vergleichen Sie die Größen von links und Mitte und platzieren Sie die kleinen Elemente im neuen Raum

3. Wiederholen Sie Schritt 2, bis eines der Sequenzen wurden durchlaufen

　4. Kopieren Sie die verbleibenden Elemente, die nicht zum neuen Raum hinzugefügt wurden, und fügen Sie sie direkt in den neuen Raum ein

Die Kernschritte des Algorithmus :

1. Verwenden Sie die Divide-and-Conquer-Methode (Rekursion), um die Sequenz aufzuteilen

2. Vergleichen Sie die Größen von links und in der Mitte und fügen Sie kleine Elemente in die neue ein Leerzeichen

sagt „Abgeschlossen“, fügen Sie den Code ein:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 排序__归并排序
{
    class 归并
    {

        public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
        static void Main(string[] args)
        {
            Sort(arr, 0, arr.Length -1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }

        public static void Sort(int []a,int left,int right)
        {
            if (left >= right) return;
            else
            {
                int mid = (left + right) / 2;                //@1
                Sort(a, left, mid);
                Sort(a, mid + 1, right);
                MergeSort(a, left, mid, right);
            }
        }

        public static void MergeSort(int []a,int left,int mid,int right)
        {
            int[] Arr = new int[right - left + 1];
            int l = left, m = mid +1 , k = 0;           //@2
            while ( m <= right && l <= mid )          //@3
            {
                if (a[l] > a[m]) Arr[k++] = a[m++];
                else Arr[k++] = a[l++];
            }
            while (m < right +1)                           //@4
            {
                Arr[k++] = a[m++];
            }
            while (l < mid +1 )  Arr[k++] = a[l++];        //@4
            for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k];
        }
    }
}

Codeinterpretation:

　@1: Die Funktion „Sort()“ schließt die Segmentierung der Sequenz ab kann nicht getrennt werden.

@2: l repräsentiert das erste Element von Sequenz 1, m repräsentiert das erste Element von Sequenz 2, k repräsentiert die Anzahl der vorhandenen Elemente im neuen Array Arr

@3: das erste Element von Sequenz 1 Vergleichen Sie es mit dem ersten Element von Sequenz 2, fügen Sie das kleine Element in Arr ein und bewegen Sie den Sequenzcursor rückwärts, bis die Elemente einer der Sequenzen verglichen sind

　@4: Der Vergleichsprozess zwischen Sequenzen 1 und Sequenz 2 kann es so aussehen, als ob Sequenz 1 vollständig zu Arr hinzugefügt wurde, Sequenz 2 jedoch nicht, dann werden die verbleibenden nicht verglichenen Elemente direkt in Arr kopiert

Zusammenfassung:

Der obige Code teilt das Array nicht im eigentlichen Sinne auf. Er füllt das geteilte Array nicht wie andere Codes in ein neues Array. Obwohl es minimal ist, ist es doch nicht so gut. Bei der Zusammenführungsoperation müssen Sie darauf achten, dass die Parameter die Grenze nicht überschreiten (ich habe lange darüber nachgedacht, warum das m über @2 gleich der Mitte +1 sein sollte Der Grund dafür ist eigentlich ganz einfach: Da mid zur linken Sequenz gehört, ist es nicht unmöglich, m = mid +1 in m = mid zu ändern Nachfolgender Code muss ebenfalls geändert werden, aber es besteht keine Notwendigkeit, einen weiteren nutzlosen Vergleich durchzuführen. Über dieses Problem habe ich wirklich lange nachgedacht ...), solange die logische Beziehung geklärt ist lässt sich leicht erfassen.

Das obige ist der detaillierte Inhalt vonSortieralgorithmus – Sortierung zusammenführen [mit Code]. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!