用Java實現計數排序算法

什麼是計數排序算法？

計數排序，一種對small ranges of integers有效的排序算法。 它的工作原理是計算輸入數組中每個值的出現次數，然後使用該信息將每個值放在輸出數組中的正確位置。

該算法的時間複雜度為O(n+k) ，其中 n 是輸入數組的大小，k 是整數的範圍。

CrunchifyCountingSortAlgo.java

這是 Java 中計數排序的完整實現。 只需將其複製到您喜歡的 IDEA 中並運行即可。

 包 crunchify.com.java.tutorials；

導入 java.util.Arrays；

/**
 * @author Crunchify.com
 * 程序：如何在java中實現計數排序算法？
 * 計數排序是一種排序算法，對數組的元素進行排序 
 * 通過計算數組中每個唯一元素的出現次數。
 */

公共類 CrunchifyCountingSortAlgo {

    public static void main(String[] args) {

        // 10 個元素的整數數組
        int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};

        crunchifyPrint("原始數組：" + Arrays.toString(crunchifyArray));
        crunchifyPrint ("\n");

        CrunchifyCountingSortAlgo crunchify = new CrunchifyCountingSortAlgo();
        crunchify.crunchifyCountingSortAlgorithm(crunchifyArray);

        crunchifyPrint ("\n");
        crunchifyPrint("Crunchify 計數排序算法的結果：" + Arrays.toString(crunchifyArray));
    }

    private static void crunchifyPrint(String s) {

        System.out.println(s);
    }


    /**
     * 作者：App Shah (Crunchify.com)
     *
     * 計數排序邏輯：
     * 這是計數排序的一種實現，一種對小範圍整數有效的排序算法。
     * 它通過計算輸入數組中每個值的出現次數來工作，
     * 然後使用該信息將每個值放在輸出數組中的正確位置。
     * 該算法的時間複雜度為O(n+k)，
     * 其中 n 是輸入數組的大小，k 是整數的範圍。
     */


    public static int[] crunchifyCountingSortAlgorithm(int[] crunchifyArray) {

        // getAsInt()：如果存在一個值，則返回該值，否則拋出 NoSuchElementException。
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = new int[crunchifyMax + 1];

        // crunchifyCount 輸入數組中每個值的出現次數
        對於 (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("加 1 到 crunchifyCount[" + crunchifyArray[i] 
                    + "]，crunchifyCount 數組現在是：" + Arrays.toString(crunchifyCount));
        }

        crunchifyPrint ("\n");

        詮釋 k = 0;
        對於 (int i = 0; i <= crunchifyMax; i++) {
            對於 (int j = 0; j < crunchifyCount[i]; j++) {
                crunchifyArray[k++] = i;
                crunchifyPrint("添加 " + i + " 到位置 " + (k - 1) 
                        + " 在輸出數組中，輸出數組現在是：" + Arrays.toString(crunchifyArray));
            }
        }

        返回 crunchifyArray；
    }

}

只需在 IntelliJ IDEA 或 Eclipse IDE 中將上述程序作為 Java 應用程序運行，您將得到如下結果。

IntelliJ IDEA 控制台結果

原始數組：[9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


向 crunchifyCount[9] 加 1，crunchifyCount 數組現在是：[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
將 1 添加到 crunchifyCount[3]，crunchifyCount 數組現在是：[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
將 1 添加到 crunchifyCount[6]，crunchifyCount 數組現在是：[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
將 1 添加到 crunchifyCount[6]，crunchifyCount 數組現在是：[0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
將 1 加到 crunchifyCount[1]，crunchifyCount 數組現在是：[0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
將 1 添加到 crunchifyCount[12]，crunchifyCount 數組現在是：[0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
將 1 添加到 crunchifyCount[32]，crunchifyCount 數組現在是：[0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
將 1 添加到 crunchifyCount[29]，crunchifyCount 數組現在是：[0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
將 1 添加到 crunchifyCount[2]，crunchifyCount 數組現在是：[0, 1, 1, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
將 1 添加到 crunchifyCount[9]，crunchifyCount 數組現在是：[0, 1, 1, 1, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
將 1 添加到 crunchifyCount[3]，crunchifyCount 數組現在是：[0, 1, 1, 2, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]


將 1 加到輸出數組中的位置 0，輸出數組現在是：[1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]
將 2 添加到輸出數組中的位置 1，輸出數組現在是：[1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
將 3 添加到輸出數組中的位置 2，輸出數組現在是：[1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]
將 3 添加到輸出數組中的位置 3，輸出數組現在是：[1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]
將 6 添加到輸出數組中的位置 4，輸出數組現在是：[1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]
將 6 添加到輸出數組中的位置 5，輸出數組現在是：[1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]
將 9 添加到輸出數組中的位置 6，輸出數組現在是：[1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]
將 9 添加到輸出數組中的位置 7，現在輸出數組為：[1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]
將 12 添加到輸出數組中的位置 8，輸出數組現在是：[1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]
將 29 添加到輸出數組中的位置 9，輸出數組現在是：[1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]
將 32 添加到輸出數組中的位置 10，輸出數組現在是：[1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]


Crunchify 計數排序算法的結果：[1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

進程結束，退出代碼為 0 

如果您在運行計數排序算法 Java 程序時遇到任何問題，請告訴我。