JAVA十大排序算法之计数排序详解

计数排序概述

计数排序是一种非比较排序算法，它的时间复杂度为O(n+k)，其中k是整数的范围。和桶排序一样，计数排序假设输入的数组中元素是平均分布的，但它不适用于元素范围过大的情况。

计数排序算法的思想：对于给定的一组数据，统计出小于等于这组数据中每个数的个数，利用这个统计信息，直接将每个元素放到它在输出数组中的位置上，从而达到排序的目的。

计数排序除了实现简单，而且相对于其他排序算法而言，它的效率比较高。但是，其缺点是比较难以应用到范围很大的数的排序中。

计数排序流程

计数排序的基本思想是将输入的数值转化为键存储在额外开辟的数组空间中，然后依次把计数大于1的填充回原始数组。以下是计数排序的具体流程：

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为 i 的元素出现的次数，存入数组C的第 i 项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素 i 放在新数组的第C(i)项，每放一个元素就将C(i)减去1；

计数排序Java代码实现

public static void countSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int max = arr[0], min = arr[0];
    // 找出数组中最大值和最小值
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }

    int[] countArr = new int[max - min + 1];
    Arrays.fill(countArr, 0);
    // 统计每个值出现的次数
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - min]++;
    }
    // 累加计数
    for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i - 1];
    }

    int[] sortedArr = new int[arr.length];
    // 反向填充目标数组
    for (int i = arr.length - 1; i >= 0; i--) {
        sortedArr[countArr[arr[i] - min] - 1] = arr[i];
        countArr[arr[i] - min]--;
    }

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

计数排序的示例

下面展示一个简单的计数排序示例。

int[] arr = new int[]{3, 1, 4, 8, 5, 7, 6, 9, 2, 0};
countSort(arr);
System.out.println(Arrays.toString(arr));

输出结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

上述示例中，我们定义了一个包含10个元素的整型数组，然后调用countSort函数进行排序。计数排序根据上述的步骤进行排序，最终输出结果是有序的数组。