Java-Sortierung Beispiel für InsertionSort-Einfügungssortierung

Einfügesortierung の Implementierung

---

Die Einfügungsart ist wie das Abschließen einer Wette, z. B. eine Doppelschnalle. Beim Kartenziehen nimmt man jeweils eine Karte und vergleicht diese Karte nacheinander mit den vorherigen Karten. Wählen Sie, wo diese Karte eingelegt werden soll, und spielen Sie die Karten reibungsloser ab, nachdem Sie die Reihenfolge festgelegt haben. Andernfalls wäre es schwierig, sie einzeln zu finden. Es ist auch nicht förderlich für die Gesamtsituation des Kartenspiels. Schauen Sie sich das Bild unten an

Unter der Annahme, dass die Kreuz-7 zum ersten Mal gezogen wird, ist keine Sortierung erforderlich. Weil es nur eine Karte gibt

, dann ziehe ich Kreuz 10 . Da 10 größer als 7 ist, ist keine Sortierung erforderlich.

Dann Karten ziehen. Ich habe festgestellt, dass ich 5 Kreuze gezogen habe . Zögern Sie zu diesem Zeitpunkt nicht, 14 Uhr ist wirklich keine große Sache. Karten entschieden abwerfen

Dann vergleichen wir 5 und 10. 5 ist weniger als 10, also tauschen Sie die Plätze.

Nehmen Sie 5 und vergleichen Sie es mit 7. 5 ist kleiner als 7. Vertauschen Sie also die Positionen von 5 und 7, um zu erhalten.

Es ist zu diesem Zeitpunkt bereits sortiert. Das Prinzip ist so.

Weil es relativ einfach ist. Fügen Sie den Code direkt ein

// O(n^2) 最坏的情况
    // 最好的情况 O(n)
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i ; j > 0; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }
    
    public static void sort(Comparable[] a, int low, int hi) {
        for (int i = low; i <= hi ; i++) {
            for (int j = i ; j > low; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }

InsertSort

Leistungsanalyse

Das schlimmste Szenario ist Die jeweils gezogene Karte ist die kleinste. Zu diesem Zeitpunkt müssen Sie jedes Mal vom Schwanz zum Kopf wechseln. Die Zeit ist proportional zu N^2

Im besten Fall wurde sie sortiert. Weil es bereits sortiert ist. Die jeweils gezogenen Karten müssen also nicht sortiert werden. Die Zeit ist proportional zu N

Das obige ist der detaillierte Inhalt vonJava-Sortierung Beispiel für InsertionSort-Einfügungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!