Zählsortierung

Hier ist ein Sortieralgorithmus, der für ein Array von Ganzzahlen oder Strukturen verwendet werden kann, die durch eine Ganzzahl verschlüsselt sind. Besonders nützlich, wenn der Bereich der Ganzzahlen in der Größenordnung der Eingabegröße liegt.

Die Hauptidee besteht darin, die Häufigkeit des Auftretens der ganzen Zahlen zu bestimmen und diese zur Bestimmung der Sortierreihenfolge zu verwenden.

Ein Beispiel: Angenommen, wir erhalten das Array {1,3,1,2}.

Bestimmen Sie zunächst den Bereich der Ganzzahlen, Max und Min, 1 und 3 für diese Eingabe.

Als nächstes erstellen Sie ein Array, nennen Sie es das Counts-Array, das die Größe des Ganzzahlbereichs + 1 hat, in diesem Fall also 3 (3-1 + 1).
Durchlaufen Sie das Eingabearray und erhöhen Sie dabei die Anzahl der entsprechenden Einträge. Die Anzahl eines bestimmten Eingabewerts wird bei counts[value - min] abgelegt. Für die gegebene Eingabe speichert counts[0] die Anzahl für den Wert 1.

Dies ergibt das Counts-Array: {2,1,1}

Bestimmen Sie nun die kumulativen Zählungen, die im Wesentlichen counts[i] = counts[i-1]+counts[i] sind.

Dies ergibt das kumulative Zählungsarray: {2,3,4}

Erstellen Sie ein Ausgabearray für die sortierte Eingabe.

Jetzt durchlaufen Sie die Eingabe in umgekehrter Reihenfolge.

Rufen Sie bei jedem Schritt die kumulative Anzahl für den Wert im Eingabearray ab. Der Wert wird am Ausgabe-Array-Index platziert, der der abgerufenen Anzahl entspricht – 1. Anschließend wird der kumulative Zählwert dekrementiert.

Im ersten Schritt wird der Wert 2 abgerufen und eine kumulative Zählung von 3. Der Wert sollte bei Index 2 (3-1) in der Ausgabe platziert werden.

In der nächsten Iteration beträgt der Wert 1 und die kumulative Anzahl 2; also wird diese „1“ an Index 1 (2-1) der Ausgabe platziert.

Fortfahrend, der Wert 3 und die kumulative Zählung 4; Platzieren Sie es an Index 3 der Ausgabe.

Schließlich der Wert 1 zum zweiten Mal und eine kumulative Zählung von 1 (da die Zählung beim ersten Mal dekrementiert wurde); also wird diese „1“ am Index 0 der Ausgabe platziert.

Sehen Sie, wie die umgekehrte Iteration die Reihenfolge gleicher Elemente beibehält und die Sortierung „stabil“ macht

Das resultierende sortierte Array ist {1,1,2,3}

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min+1)
    for _, v := range in {
        counts[v-min]++
    }
    // determine cumulative counts
    for i := 1; i < len(counts); i++ {
        counts[i] = counts[i-1] + counts[i]
    }
    // create the output array
    out := make([]int, len(in))
    for i := range in {
        v := in[len(in)-1-i]
        out[counts[v-min]-1] = v
        counts[v-min]--
    }
    return out
}

Kann es effizienter gemacht werden? Hinterlassen Sie unten Ihre Kommentare und Vorschläge.

Danke!

Den Code für diesen Beitrag und alle Beiträge dieser Reihe finden Sie hier

以上是Zählsortierung的详细内容。更多信息请关注PHP中文网其他相关文章！