Codebeispiel für die Java-Implementierung der Zählsortierung (CountingSort)

Dieser Artikel enthält Codebeispiele zur Java-Implementierung der Zählsortierung (CountingSort). Ich hoffe, dass er Ihnen weiterhilft.

Die Zählsortierung ist eine spezielle Art der Bucket-Sortierung.

Wenn n Daten sortiert werden sollen und der Bereich nicht groß ist, können wir den Maximalwert K nehmen und die Daten in K Buckets verteilen,

jeder Die Daten in den Buckets sind alle das Gleiche (das spart Zeit beim Sortieren in den Eimern), und dann werden sie der Reihe nach herausgenommen.

Natürlich ist Zählen und Sortieren einfach zu sagen, aber es gibt einige Dinge, die beim Schreiben schwer zu verstehen sind.

Zum Beispiel haben wir jetzt 8 Zahlen: 2, 5, 3, 0, 2, 3, 0, 3. Um sie zu sortieren, können wir zuerst ihren Maximalwert von 5 ermitteln und dann den Bereich bestimmen . 0-5,

Wir beantragen einen Speicherplatz von 0-5, um die Nummer jeder Zahl zu berechnen, die jeder Position entspricht.

Das Bild unten zeigt die Daten im Speicherbereich 0-5. Wir können sehen, dass 0 zweimal erscheint, 1 0-mal erscheint, 2 zweimal erscheint, 3 dreimal erscheint und 4 0-mal erscheint erschien einmal.

Gleichzeitig können wir auch einige Regeln zusammenfassen. Beispielsweise sehen wir jetzt, dass an der Position von c[2] 2 zweimal erscheint und vor 2 c[0] + c[1] hat insgesamt 2 Elemente, daher entspricht c[2] den Positionen dieser beiden 2en im ursprünglichen Array, nämlich 2 und 3. Wir können die Regel aufstellen, dass die Position von c[2] = c [0] + c[1] und die folgende c[3 ]-Position = c[2] + c[1], wir summieren sie der Reihe nach wie folgt: Dann scannen wir das ursprüngliche Array 2, 5, 3, 0, 2, 3, 0, 3, jedes Mal, wenn wir auf eine Zahl stoßen, setzen wir diese Zahl in den Index des c-Arrays ein, um nach der Sortierung den tatsächlichen Index des aktuellen Elements zu erhalten.

Meine Java-Implementierung lautet wie folgt:

package com.structure.sort;
/**
 * @author zhangxingrui
 * @create 2019-01-30 13:45
 **/
public class CountingSort {
    public static void main(String[] args) {
        int[] numbers = {3, 9, 2, 1, 8, 7, 6, 10, 9};
        // 假设数组中存储的都是非负整数
        countingSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 计数排序
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(int[] numbers){
        int n = numbers.length;
        int maxNumber = numbers[0];
        for(int i = 1; i < n; ++i){
            if(numbers[i] > maxNumber)
                maxNumber = numbers[i];
        }
        int[] r = new int[n];
        int[] c = new int[maxNumber + 1];
        for(int i = 0; i < n; ++i){
            c[numbers[i]]++;
        }
        for(int i = 1; i <= maxNumber; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;
        }
        for(int i = 0; i < n; ++i){
            numbers[i] = r[i];
        }
    }
}

Der Schlüsselcode:

for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;5         
            }

Rufen Sie den sortierten Index aus dem c-Array ab.

Das obige ist der detaillierte Inhalt vonCodebeispiel für die Java-Implementierung der Zählsortierung (CountingSort). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!