排序算法 —— 计数排序

我就是我 2022-10-16 12:29 164阅读 0赞

# 引言 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70][]

# 一、代码实现 #

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)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70]: /images/20221014/520db2c62dbd4bf683ce32792bf8331e.png