Algorithmusübersicht/Ideen
Die Zusammenführungssortierung basiert auf einer Strategie namens "Divide und Eroberung". Die Grundidee ist wie folgt:
1. Für zwei bestellte Arrays, um sie in ein bestelltes Array zu verschmelzen, können wir den folgenden Code problemlos schreiben:
// Sowohl A als auch B ist aufstock. while (i <= A.Length && j <= b.Length) {if (a [i] <= b [i]) {c [k ++] = a [i ++]; } else {c [k ++] = b [j ++]; }} while (i <= a.Length) {c [k ++] = a [i ++]; }} Es ist leicht zu erkennen, dass ein solcher Zusammenführungsalgorithmus effizient ist und seine Zeitkomplexität O (n) erreichen kann.
2. Wenn es ein ungeordnetes Array gibt, das sortiert werden muss, aber seine beiden vollständig geteilten Subarrays A und B separat bestellt werden, können wir sie auch mit Hilfe des obigen Code leicht implementieren.
3. Also, was soll ich tun, wenn A und B ungeordnet sind? Sie können sie in kleinere Arrays aufteilen.
4. Wenn Sie es bis zum kleinsten teilen, hat jedes Subtarray nur ein Element, es kann als geordnetes Array angesehen werden.
5. Beginnen Sie mit diesen kleinsten Arrays, verschmelzen sie mit den obigen Schritten und das gesamte Array ist angeordnet.
Kurz gesagt, die Zusammenführungssortierung besteht darin, eine Rekursion zu verwenden, das Array zuerst in ein Subarray zu zersetzen und dann das Array zu verschmelzen.
Beispiel
Hier ist ein Beispiel. Wenn Sie das Array A = {2,1,3,5,2,3} sortieren möchten, teilen Sie das Array das Array in zwei SubaRrays: {2,1,3} und {5,2,3}. Nach der Sortierung dieser beiden Subtarrays werden sie {1,2,3} und {2,3,5} und verschmelzen dann die beiden Arrays, um das endgültige geordnete Array zu erhalten. Die Code -Implementierung ist wie folgt:
void sort (int [] a) {int [] aux = new int [A.Length]; // Aux -Array mergesOrT (a, 0, A.Length - 1, aux);} void mergesort (int [] a, int lo, int hi, int [] aux) {if (hi <= lo) return; int Mid = lo + (hi - lo) / 2; mergesort (a, lo, mid, aux); mergesort (a, mid + 1, hi, aux); merge (a, lo, mid, hi, aux);} void merge (int [] a, int lo, int mid, int hi, int [] aux) {int i = lo, j = Mid + 1; für (int k = lo; k <= hi; k ++) {aux [k] = a [k]; } für (int k = lo; k <= hi; k ++) {if (i> mid) a [k] = aux [j ++]; sonst wenn (j> hi) a [k] = aux [i ++]; sonst wenn (aux [i] <= aux [j]) a [k] = aux [i ++]; sonst a [k] = aux [j ++]; }} Eine weitere Implementierung: Bottom-up-Zusammenführungssortierung
In der obigen Implementierung ist es gleichbedeutend mit der Aufteilung eines großen Problems in kleine Probleme und der separaten Lösung und dann der Antworten auf alle kleinen Probleme, um das gesamte große Problem zu lösen. Das Teilen der Art eines großen Arrays in ein kleines Array Die Art von Sorte ist eine Sortierung von Top-Down. Es gibt eine weitere Implementierung, die das Bottom-up-Sortieren ist, dh zuerst zusammenzusetzen und dann vier und vier zusammenzuführen ... die Code-Implementierung lautet wie folgt:
void sort (int [] a) {int n = A.Length; int [] aux = new int [n]; für (int sz = 1; sz <n; sz + = sz) {für (int lo = 0; lo <n - sz; lo + = sz + sz) {// In jeder Runde des Zusammenführens kann das zweite Sub -Array, das beim letzten Mal kleiner als der erste Sub -Array -Merge (a, lo, lo + sz - 1), math.Min (Math.M. }}}