排序算法 —— 计数排序_计数排序对于顺序递增 递减 随机的数据

引言

计数排序是桶排序思想的一种具体实现，针对一些具有特殊限制的样本数据，如公司员工年龄，那么样本数据本身就一定在0~200之间，针对这样的数据，使用从0到200 的桶数组，桶的位置已经是有序的，只需要将对应年龄的数据放入对应的桶，比如，24岁的员工有10人，那么就往 24 号桶中放10个数据。将所有员工年龄数据放入桶数组中后，只需要再次将它们放回到原数组就可以实现排序了：

一、代码实现

    public static void countSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        // 找到数组中的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 为了能够覆盖到最后一个值，需要+1
        int[] buckets = new int[max + 1];
        // 桶的下标记录数据，桶中的元素记录数据数量
        for (int i = 0; i < arr.length; i++) {
            buckets[arr[i]]++;
        }
        int i = 0;
        // 循环桶数组
        for (int j = 0; j < buckets.length; j++) {
            // 如果桶中有元素，那么执行放回操作，并递减，直到取出所有元素
            while (buckets[j]-- > 0) {
                // 桶下标代表数据本身，因此直接以下标作为返回的数据
                arr[i++] = j;
            }
        }
    }

二、计数排序的时间复杂度

计数排序是多个循环操作的累加。

首先是遍历数组，求得一个最大值，来决定桶的个数，时间复杂度是O(N)；

然后是将所有元素计数到辅助的桶数组中，时间复杂度是O(N);

随后，通过遍历桶数组，选出存有数据的桶，并依次取出累计个数的元素并返回到原数组中，虽然for循环嵌套了while循环，但实际上while只是把桶中的元素全部取出，其for + while操作的次数一定等于元素个数N，因此时间复杂度同样是O(N)。

所以，最后得出计数排序的时间复杂度是 O(N) + O(N) + O(N) = O(3N) 忽略倍数即为 O(N)。