Überlegen Sie zunächst, wie Sie zwei geordnete Sequenzen zusammenführen. Das ist ganz einfach. Vergleichen Sie einfach die erste Nummer der beiden Sequenzen und nehmen Sie zuerst die kleinere. Löschen Sie dann die Nummer in der entsprechenden Sequenz. Vergleichen Sie sie dann. Wenn eine der Spalten leer ist, entnehmen Sie einfach die Daten der anderen Spalte einzeln.
Kopieren Sie den Codecode wie folgt:
Code anzeigen
//Geordnete Arrays a[] und b[] zu c[] zusammenführen
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
anders
c[k++] = b[j++];
}
während (i < n)
c[k++] = a[i++];
während (j < m)
c[k++] = b[j++];
}
Es ist ersichtlich, dass die Effizienz der Zusammenführung geordneter Sequenzen relativ hoch ist und O(n) erreichen kann.
Nachdem wir das obige Problem des Zusammenführens geordneter Sequenzen gelöst haben, schauen wir uns die Zusammenführungssortierung an. Die Grundidee besteht darin, das Array in zwei Gruppen A und B zu unterteilen. Wenn die Daten in diesen beiden Gruppen alle geordnet sind, können diese beiden Mengen problemlos erstellt werden der Daten werden sortiert. Wie hält man die Daten in diesen beiden Gruppen in Ordnung?
Die Gruppen A und B können in zwei Gruppen unterteilt werden. Wenn die getrennte Gruppe nur einen Datenwert hat, kann analog davon ausgegangen werden, dass die Gruppe die Ordnung erreicht hat, und dann können die beiden benachbarten Gruppen zusammengeführt werden. Auf diese Weise wird die Zusammenführungssortierung abgeschlossen, indem das Array zunächst rekursiv zerlegt und dann zusammengeführt wird.
Kopieren Sie den Codecode wie folgt:
Code anzeigen
//Führt zwei geordnete Sequenzen zusammen: a[first...mid] und a[mid...last].
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = Mitte, n = zuletzt;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
anders
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
während (j <= n)
temp[k++] = a[j++];
für (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (erster < letzter)
{
int mid = (erster + letzter) / 2;
mergesort(a, first, mid, temp); //Linke Seite wird sortiert
mergesort(a, mid + 1, last, temp); //Die rechte Seite wird sortiert
mergearray(a, first, mid, last, temp); //Füge die beiden geordneten Arrays zusammen
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
Die Effizienz der Zusammenführungssortierung ist relativ hoch. Angenommen, die Länge der Sequenz beträgt N. Es sind logN Schritte erforderlich, um die Sequenz in Dezimalsequenzen zu unterteilen. Die zeitliche Komplexität kann als O( aufgezeichnet werden. N), also ist die Summe O(N*logN). Da die Zusammenführungssortierung jedes Mal auf benachbarte Daten angewendet wird, sind mehrere Sortiermethoden der Zusammenführungssortierung (Schnellsortierung, Zusammenführungssortierung, Hill-Sortierung, Heap-Sortierung) in O(N*logN) ebenfalls relativ effizient.