So implementieren Sie den Zählsortieralgorithmus mit Java

So implementieren Sie den Zählsortieralgorithmus in Java

Die Zählsortierung ist ein Sortieralgorithmus ohne Vergleich. Seine Hauptidee besteht darin, zu zählen, wie oft jedes Element im Array erscheint, und das Element dann an der richtigen Position zu platzieren basierend auf der Häufigkeit, mit der es erscheint. Die zeitliche Komplexität der Zählsortierung beträgt O(n+k), wobei n die Länge der zu sortierenden Sequenz und k der Bereich des größten Elements in der zu sortierenden Sequenz ist.

In Java können wir das folgende Codebeispiel verwenden, um den Zählsortieralgorithmus zu implementieren:

public class CountingSort {
    public static void countingSort(int[] array) {
        int n = array.length;
        
        // 找到待排序序列中的最大值
        int max = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        // 创建一个计数数组，并初始化为0
        int[] count = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            count[i] = 0;
        }
        
        // 统计每个元素在待排序序列中出现的次数
        for (int i = 0; i < n; i++) {
            count[array[i]]++;
        }
        
        // 根据计数数组构建有序序列
        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                array[index] = i;
                index++;
                count[i]--;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] array = {9, 1, 5, 3, 7, 3, 8, 2, 6};
        
        System.out.println("排序前：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        countingSort(array);
        
        System.out.println("排序后：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Im obigen Code suchen wir zuerst den Maximalwert in der zu sortierenden Sequenz, erstellen dann ein Zählarray und fügen die Zahl hinzu Anzahl der Vorkommen jedes Elements. Die Statistiken befinden sich im Zählarray. Als nächstes erstellen wir eine geordnete Sequenz basierend auf dem Zählarray. Die spezifische Operation besteht darin, die Elemente im Zählarray in die Sequenz einzufügen, die entsprechend der Anzahl der Vorkommen sortiert werden soll. Wenn wir schließlich die countingSort-Methode aufrufen und die geordnete Sequenz drucken, können wir die Ergebnisse der Zählsortierung sehen.

Es ist zu beachten, dass die Zählsortierung bestimmte Einschränkungen hinsichtlich des Bereichs der zu sortierenden Elemente in der Sequenz hat und nur auf nichtnegative Ganzzahlsequenzen anwendbar ist. Wenn die zu sortierende Sequenz negative Zahlen oder Elemente anderer Datentypen enthält, ist eine entsprechende Verarbeitung erforderlich, bevor der Zählsortieralgorithmus verwendet werden kann.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Zählsortieralgorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!