当前位置：首页 > article >正文

Java算法之计数排序（Counting Sort）

article 2025/2/1 1:59:57

简介

计数排序是一种线性时间复杂度的排序算法，它不依赖于元素之间的比较，而是通过统计数组中每个元素出现的次数，然后根据这些统计信息对元素进行排序。这种算法特别适用于整数且整数的范围不是非常大时。

算法步骤

找出数组中的最大值。
创建一个计数数组，长度为最大值加一。
遍历原数组，对每个元素在计数数组中对应的位置加一。
再次遍历计数数组，将每个非零元素按顺序累加到原数组。

//countingSort 方法接受数组和最大值作为参数，执行计数排序。
//首先创建一个计数数组，长度为最大值加一。
//遍历原数组，统计每个元素出现的次数。
//再次遍历计数数组，将非零元素累加到原数组。
//main 方法中，我们初始化一个数组，找出最大值，然后调用 countingSort 方法进行排序，并打印排序后的结果。
public class CountingSort {
    // 计数排序方法
    public static void countingSort(int[] arr, int maxVal) {
        int n = arr.length;
        int[] count = new int[maxVal + 1]; // 创建计数数组

        // 统计每个元素出现的次数
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }

        // 将计数数组中非零元素累加到原数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        int maxVal = getMaxVal(arr); // 找出数组中的最大值

        countingSort(arr, maxVal);

        // 打印排序后的数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    // 辅助方法，找出数组中的最大值
    private static int getMaxVal(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
}