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.

Erstellen Sie als Nächstes ein Array und nennen Sie es das Counts-Array. Das entspricht der Größe des Ganzzahlbereichs 1, 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 entsprechend der abgerufenen Anzahl - 1 platziert. Anschließend wird der kumulative Zählwert dekrementiert.

Im ersten Schritt wird der Wert 2 abgerufen und eine kumulative Anzahl von 3. Der Wert sollte an 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.

Weiter der Wert 3 und die kumulative Anzahl 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' an 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 



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

Danke!

Der Code für diesen Beitrag und alle Beiträge dieser Serie finden Sie hier