Rekursion Merge-Sort -
Dies ist ein code aus Einführung in die Programmierung mit Java zu Merge-Sort. Diese Methode nutzt eine Rekursion Implementierung.
public class MergeSort {
2 /** The method for sorting the numbers */
3 public static void mergeSort(int[] list) {
4 if (list.length > 1) {
5 //Merge sort the first half
6 int[] firstHalf = new int[list.length / 2];
7 System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
8 mergeSort(firstHalf);
9
10 //Merge sort the second half
11 int secondHalfLength = list.length - list.length / 2;
12 int[] secondHalf = new int[secondHalfLength];
13 System.arraycopy(list, list.length / 2,
14 secondHalf, 0, secondHalfLength);
15 mergeSort(secondHalf);
16
17 //Merge firstHalf with secondHalf into list
18 merge(firstHalf, secondHalf, list);
19 }
20 }
Meine Frage: ist in Zeile 8 ruft der rekursions-Methode zurück, um "mergeSort"? Wenn vom Anfang der Methode, die "firstHalf" - array wird erneut erstellt und die Länge der Hälfte kurz. Ich denke, die "firstHalf" kann nicht neu erstellt und die Länge sollte nicht verändert werden, wenn ein array ist schon definiert.
Hier ist die ganze code-link: Merge-Sort Java.
firstHalf
neu erstellt, wie es es gehört zum Umfang der(list.length > 1)
so wird für jeden AufrufMergeSort
mit einemlist.length > 1
erhalten Sie und andereint[] firstHalf
. Das war deine Frage oder?- Ich ermutige Sie, schauen Sie unter diesem link algs4.cs.princeton.edu/22mergesort
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist für Anfänger gedacht. Ja, genau, ich dachte das gleiche, wenn ich auf diese vor. Ich konnte nicht glauben, dass die array-Größe dynamisch ändern können. Verstehen, in dem code unten,
array l and array r
erstellt werden, mit verschiedenen Größen fürevery recursive call
. Nicht zu verwechseln mit der auf dieser.Ja, das ist niemals möglich, dass die array-Größe dynamisch ändert, für einen Anfänger wie dich und mich. Aber, es ist eine Ausnahme, gut, es gibt Ausnahmen. Wir sehen Sie sehr Häufig, wie wir vorankommen.
Seine verwirrend, aber es ist wirklich interessant, wenn Sie nachdenken über es. Seine Tiefe. Merge-sort implementiert werden können, die auf ganz unterschiedliche Weise, aber das zugrunde liegende Konzept der Rekursion ist dieselbe. Verwirrt nicht hier, ist es besser Sie Folgen einem anderen Weg, es zu tun, video:
Merge-sort-first takes, eine Liste oder ein array. Können sich vorstellen, die
Nun das Endziel ist split das array rekursiv, bis es erreicht einen Punkt, an dem es keine-Elemente (nur-eine). Und ein
single element is always sorted
.Finden Sie in der Basis-Fall in der folgenden code:
Sobald es erreicht zu single-element, Sortieren und verschmelzen Sie zurück. Auf diese Weise erhalten Sie eine vollständige sortierte array zurück, das ist einfach zu verschmelzen. Der einzige Grund, warum wir tun, was dieser nicht-Sinn ist, um eine bessere run-time-Algorithmus, der O(nlogn).
Weil alle anderen Sortier algos (
insertion, bubble, and selection
) nehmen O(n2), das ist viel, zu viel, in der Tat. So muss die Menschheit herauszufinden, die bessere Lösung. Dessen Notwendigkeit für die Menschheit sehr wichtig. Ich weiß, das ist ärgerlich, ich hatte mich durch dieses nicht-Sinn.Bitte tun Sie etwas Forschung auf Rekursion, bevor Sie versuchen, auf diese. Verstehen die Rekursion deutlich. Halten Sie alle diese Weg. Nehmen Sie eine einfache Rekursion Beispiel und mit der Arbeit beginnen. Nehmen Sie einen faktoriellen Beispiel. Seine ein schlechtes Beispiel, aber es ist einfach zu verstehen.
Top-down-MergeSort
Siehe mein code, es ist schön und einfach. Wieder, beide sind nicht leicht zu verstehen, auf Ihrem ersten Versuch. Sie müssen in Kontakt mit der Rekursion, bevor Sie versuchen, diese Dinge zu verstehen. Alle die besten.
Als es war wies darauf hin, durch Emz: Dies ist aufgrund des Umfangs Gründen. Wird eine lokale variable ein neues Objekt.
[
Hier ist eine alternative Implementierung von merge-sort, das ist
bottom-up MergeSort