用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 程序时遇到任何问题，请告诉我。