在 java 中实现计数排序？

计数排序（Counting Sort）是一种非比较排序算法，它的核心思想是统计待排序序列中每个元素出现的次数，然后根据元素出现次数进行排序。计数排序的时间复杂度为 O(n+k)，其中 n 是待排序序列的长度，k 是序列中元素的取值范围。

下面是 Java 代码实现计数排序的示例：

javaCopy codepublic static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().orElse(0);
    int min = Arrays.stream(arr).min().orElse(0);
    int k = max - min + 1;

    int[] count = new int[k];
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }

    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    int[] sorted = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        sorted[--count[arr[i] - min]] = arr[i];
    }

    System.arraycopy(sorted, 0, arr, 0, arr.length);
}

上述代码实现了计数排序，其中：

max 和 min 分别是待排序序列中的最大值和最小值；
k 是序列中元素的取值范围；
count 是长度为 k 的计数数组，用于统计序列中每个元素出现的次数；
第一个循环遍历待排序序列，统计每个元素出现的次数；
第二个循环用于累加计数数组中的值，得到每个元素在排序后序列中的最终位置；
第三个循环遍历待排序序列，将每个元素放到其在排序后序列中的位置；
最后将排序后序列复制到原序列中。

原文链接：codingdict.net

在 java 中实现计数排序？

热门标签