Arrays.sort (Objekt [] a) - wie wird es implementiert?

Gibt es irgendwelche Ressourcen, wie der von Arrays.sort (Object [] a) verwendete mergeSort implementiert ist? Obwohl es ziemlich gut dokumentiert ist, fällt es mir schwer, es zu verstehen (vor allem, warum src und dest umgeschaltet werden, wenn mergeSort() rekursiv aufgerufen wird).Arrays.sort (Objekt [] a) - wie wird es implementiert?

Quelle

2010-02-07 helpermethod

http://www.docjar.com/html/api/java/util/Arrays.java.html hier ist der Quellcode – Bozho

Bozho, du hättest das an eine Antwort schreiben sollen! – Will

Sieht so aus, als ob die echte Arbeit in Zeile 486 beginnt. – MatrixFrog

Here is the source von java.util.Arrays.

Eigentlich haben Sie diesen Quellcode im JDK - öffnen Sie einfach java.util.Arrays in Ihrer IDE und der Quellcode + die Kommentare werden angezeigt. Wenn Sie keine IDE haben, schauen Sie sich

Dann legen Sie es in Ihre IDE und verfolgen, wie es funktioniert.

Put-Haltepunkte (und ein Programm im Debug-Modus laufen)
Verwendung System.out.println(..)
Änderung Teile davon zu sehen, wie sie reflektiert werden.
lesen Sie die wikipedia article about merge sort
achten Sie auf diesen Kommentar: // Recursively sort halves of dest into src

Quelle

2010-02-07 20:02:55 Bozho

Es ** erscheint ** das OP sah bereits die Quelle (da er/sie die Tatsache erwähnt, dass die 'src'- und' dest'-Felder umgeschaltet werden, wenn rekursiv aufgerufen wird), aber es ist schwer, die Logik zu verstehen. –

hm, ja. Ich habe einige Hinweise gegeben, wie man es besser verstehen kann. – Bozho

Ich könnte natürlich falsch liegen ... Wie auch immer, ich wollte dem OP vorschlagen, den Debugger * des armen Mannes zu benutzen (indem er einige System.out.println in den Algorithmus einfügt), aber Sie haben mich dazu geschlagen! –

ich je mit Ihnen die gleiche Verwirrung hatte. Meines Erachtens ist der Grund für diesen Wechsel sehr einfach - machen Sie den folgenden Schritt einfacher. 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]; 
    } 

}

Oben ist die Implementierung ohne Wechsel, aus dem Code, können Sie sehen, wir brauchen noch einen Schritt in der Zusammenführung - zurück kopieren. Ich denke, dass die Benennung von Parametern in mergeSort ein wenig verwirrt ist, da das src ein Hilfsarray ist, das nur im Zusammenführungsschritt verwendet wird. Es ist besser, es mit aux zu benennen (wir können es sogar aus der Methodensignatur entfernen und eine lokale Variable erstellen) beim Zusammenführen). Und dest ist das Ergebnis-Array.

Quelle

2010-11-19 07:47:32 lostinmoney

Arrays.sort (Objekt [] a) - wie wird es implementiert?

Antwort

Verwandte Themen