Javaを使用してカウントソートアルゴリズムを実装する方法

Java を使用してカウント並べ替えアルゴリズムを実装する方法

カウント並べ替えは、非比較並べ替えアルゴリズムです。その主なアイデアは、各要素が出現する回数をカウントすることです。配列内に要素を配置し、出現回数に基づいて要素を正しい位置に配置します。カウントソートの時間計算量は O(n k) です。ここで、n はソートされるシーケンスの長さ、k はソートされるシーケンス内の最大要素の範囲です。

Java では、次のコード例を使用して、カウント ソート アルゴリズムを実装できます。

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();
    }
}

上記のコードでは、まずソートするシーケンス内の最大値を見つけてから、カウント配列を作成し、カウント配列内の各要素の出現をカウントします。次に、count 配列に基づいて順序付けされたシーケンスを構築します。具体的な操作は、count 配列内の要素を、出現回数に従って並べ替えられるシーケンスに配置することです。最後に、countingSort メソッドを呼び出して順序付けられたシーケンスを出力すると、カウント ソートの結果を確認できます。

カウントソートには、ソートされるシーケンス内の要素の範囲に一定の制限があり、非負の整数シーケンスにのみ適用できることに注意してください。ソートするシーケンス内に負の数値または他のデータ型の要素がある場合、カウントソートアルゴリズムを使用する前に適切な処理が必要です。

以上がJavaを使用してカウントソートアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。