Insertion Sort vs. Insertion Sort vs. Binary Insertion Sort

Question

Ich habe ein paar Fragen zu verschiedenen Implementierungen von Insertionsort.

Die Umsetzung 1:

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int key = a[i];
        int j   = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }

        a[j + 1] = key;
    }
}

Implementierung 2:

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        for (int j = i; j > 0 && a[j - 1] > a[j]; --j) {
            swap(a, j, j - 1);
        }
    }
}

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];

    a[i] = a[j];
    a[j] = tmp;
}

Hier ist meine erste Frage: Man sollte denken, dass die erste Version ein wenig schneller sein soll, dass die zweite Version (wegen der geringeren Zuweisungen), aber es ist nicht (oder zumindest der Unterschied es vernachlässigbar ist). Aber warum?

Zweitens, ich habe mich gefragt, dass Java Arrays.sort () -Methode verwendet auch den zweiten Ansatz (vielleicht wegen der Wiederverwendung von Code, weil die Swap-Methode an verschiedenen Orten verwendet wird, vielleicht, weil es einfacher ist, zu verstehen).

Die Umsetzung 3 (binaryInsertionSort):

    public static void binaryInsertionSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int pos            = Arrays.binarySearch(a, 0, i, a[i]);
        int insertionPoint = (pos >= 0) ? pos : -pos - 1;

        if (insertionPoint < i) {
            int key = a[i];

            // for (int j = i; i > insertionPoint; --i) {
            //     a[j] = a[j - 1];
            // }
            System.arraycopy(a, insertionPoint, a, insertionPoint + 1, i - insertionPoint);

            a[insertionPoint] = key;
        }
    }
}

Ist das binäre Insertionsort von praktischem Nutzen, oder ist es eher eine theoretische Sache? Auf kleine Arrays sind die anderen Ansätze viel schneller, und auf größere Arrays mergesort / quicksort hat eine viel bessere Leistung.

Answer 1

1. löschen falsche Behauptung
2. die Anzahl der Vergleiche in den ersten beiden 1/2 * n (n-1), mit Ausnahme derjenigen für die äußeren Schleifen.
3. Keines dieser Programme machen viel Sinn für echte Arbeit, wie sie sind, weil sie nicht über die Nutzung der Informationen zur Verfügung stellen. Zum Beispiel ist es einfach, einen Scheck an die inneren Schleife hinzufügen, um zu sehen, ob irgendwelche Swaps vorgenommen: wenn nicht, dann wird das Array sortiert und Sie können beenden, vielleicht die meiste Arbeit zu sparen. In der Praxis kann diese Art der Betrachtung der durchschnittlichen Fall dominieren.

Postscript Verpasste die Frage nach Java: Ich verstehe, dass das Java Art ein ziemlich komplexer Algorithmus, das eine Menge von speziellen Fällen verwendet, wie spezielle Sortierkästen für kleine Arrays und quicksort mit seinem schweren Heben zu tun.