Arrays.sort (Object [] a) - wie wird sie umgesetzt?

Question

Gibt es irgendwelche Ressourcen, wie der MergeSort von Arrays.sort verwendet (Object [] a) umgesetzt wird? Während es recht gut dokumentiert ist, habe ich eine harte Zeit, es zu verstehen (vor allem, warum die src und dest werden eingeschaltet werden, wenn MergeSort () rekursiv genannt werden).

Answer 1

Hier ist die Quelle von java.util.Arrays.

Eigentlich haben Sie diesen Quellcode in der JDK - nur offen java.util.Arrays in Ihrem IDE und den Quellcode + Kommentare angezeigt. Wenn Sie nicht über eine IDE haben, schauen Sie sich JDK_HOME\src.zip

Dann, setzen Sie es in Ihrem IDE und verfolgen, wie es funktioniert.

• setzen Haltepunkte (und ein Programm im Debug-Modus ausgeführt wird)
• Verwendung System.out.println(..)
• Änderung Teile davon zu sehen, wie sie reflektiert werden.
• Lesen Sie die Wikipedia-Artikel über Mergesort
• Achten Sie auf diesen Kommentar: // Recursively sort halves of dest into src

Answer 2

Ich hatte immer die gleiche Verwirrung mit Ihnen. Nach meinem Verständnis ist der Grund für diese Schalt sehr einfach - zu erleichtern Schritt gefolgt verschmelzen. Keine Magie.

    private static void mergeSortWithoutSwitch(Object[] src, Object[] dest, int low, int high, int off) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i = low; i < high; i++)
            for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
                swap(dest, j, j - 1);
        return;
    }

    // Recursively sort halves of dest into src
    int destLow = low;
    int destHigh = high;
    low += off;
    high += off;
    int mid = (low + high) >>> 1;
    mergeSortWithoutSwitch(src, dest, low, mid, off);
    mergeSortWithoutSwitch(src, dest, mid, high, off);

    // If list is already sorted, just copy from src to dest. This is an
    // optimization that results in faster sorts for nearly ordered lists.
    if (((Comparable) dest[mid - 1]).compareTo(dest[mid]) <= 0) {
        return;
    }

    // Merge sorted halves (now in src) into dest
    for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
        if (q >= high || p < mid && ((Comparable) dest[p]).compareTo(dest[q]) <= 0)
            src[i] = dest[p++];
        else
            src[i] = dest[q++];
    }

    // copy back
    for (int i = destLow; i < destHigh; i++) {
        dest[i] = src[i];
    }

}

Vor der Implementierung ist ohne Umschalten aus dem Code, können Sie uns bei der Zusammenführung benötigen einen weiteren Schritt sehen - zurückkopieren. Ich denke, die Namensgebung Parameter in MergeSort ein wenig verwirrt, da die src Hilfsgruppe ist, die nur im Vereinigungsschritt verwendet wird, wird es besser sein, es zu benennen mit aux (Wir können es sogar von Methodensignatur entfernen, und erstellen Sie eine lokale Variable beim Zusammenführen). Und dest ist das Ergebnis-Array.