Zwei rekursive Aufrufe in einer Merge Sort-Funktion verwirren
Ich bin seit einiger Zeit nicht mehr mit Algorithmen in Berührung und beginne in diesen Tagen, meine Konzepte zu überarbeiten. Zu meiner Überraschung erinnere ich mich zuletzt an meine Rekursionsfähigkeiten, dass ich gut darin war, aber nicht mehr. Also, ich habe eine grundlegende Frage für euch, die mich verwirrt. Bitte beachten Sie zuerst den folgenden Code.
private void mergesort(int low, int high) {
if (low < high) {
int middle = (low + high)/2 ;
System.out .println ("Before the 1st Call");
mergesort(low, middle);
System.out .println ("After the 1st Call");
mergesort(middle+1, high);
System.out .println ("After the 2nd Call");
merge(low, middle, high);
}
}
Der Funktionsaufruf
mergesort(0,7);
Und die Ausgabe ist
Vor dem 1. Anruf
Vor dem 1. Anruf
Vor dem 1. Anruf
Nach dem 1. Anruf
Nach dem 2. Anruf
Nach dem 1. Anruf
Vor dem 1. Anruf
Nach dem 1. Anruf
Nach dem 2. Anruf
Nach dem 2. Anruf
Nach dem 1. Anruf
Vor dem 1. Anruf
Vor dem 1. Anruf
Nach dem 1. Anruf
Nach dem 2. Anruf
Nach dem 1. Anruf
Vor dem 1. Anruf
Nach dem 1. Anruf
Nach dem 2. Anruf
Nach dem 2. Anruf
Nach dem 2. Anruf
Die Sache, die mich im obigen Code und Ergebnis verwirrt, ist der zweite rekursive Aufruf. Ich verstehe den Ablauf bis zur vierten Ausgabezeile (d. H. Nach dem ersten Anruf). Aber ich kann nicht verstehen, warum es (nach dem 2. Anruf) nach dem (nach dem 1. Anruf) ausgibt. Nach dem Verständnis des Codes sollte nach der Ausgabe (nach dem 1. Aufruf) die Mergesort-Funktion mit Parameter (Mitte + 1, hoch) aufgerufen und ausgegeben werden (vor dem 1. Aufruf) und mit Mergesort in den rekursiven Aufruf übergegangen werden (niedrig, mittel). Ich bin comfartable mit einer rekursiven Anruffunktionen und verstehe und bin mit foreg Fibonacci-Beispiel synchronisiert.