排序算法 --- 计数排序

前面说的那些排序算法,都是要通过比较来实现的。排序还能不通过比较来实现?是的,计数排序就是这么神奇。

一、排序思想

创建一个计数数组,利用数组下标来表示该元素,用数组下标对应的值来表示元素出现的次数。然后遍历计数数组即可。比如下标为5,元素值为2,表示5出现两次,连续写两次5即可。


欢迎大家关注我的公众号 javawebkf,目前正在慢慢地将简书文章搬到公众号,以后简书和公众号文章将同步更新,且简书上的付费文章在公众号上将免费。


1. 案例:

假如待排序列arr如下:

5   7    4    8   3    5

最大元素是8,所以创建一个最大下标为8的数组:

int[] count = new int[9];

遍历待排序列,第一个是5,所以count[5]++],第二个是7,所以count[7]++…… 最终count数组就是:

0   0   0   1   1   2   0   1   1   // 元素值
0   1   2   3   4   5   6   7   8   // 下标

最后根据count数组,可以知道,3出现一次,4出现一次,5出现两次……就可以知道排序后应该是这样的:

3   4   5   5   7   8

这样看似很完美,但是会存在两个问题。

2. 问题一:

上面的5出现了两次,最后排完序的的数组中下标为2的那个5,还是原序列中下标为0的那个5吗?也就是说,当值相同的情况下,无法保证排序后相同元素出现的顺序和排序前一致,这也就是我们说的不稳定排序。如何优化呢?

我们给之前的数组中两个5做上标记,便于区分:

小红                                      小白
5       7        4        8       3       5
  • 然后和之前一样,统计每个元素出现的次数,得到count数组:
0   0   0   1   1   2   0   1   1   // 元素值
0   1   2   3   4   5   6   7   8   // 下标
  • 接下来,对count数组进行变形,然后一个元素加上前一个元素,即:
count[i] = count[i] + count[i-1];

这样一来,count数组就变成了:

0   0   0   1   2   4   4   5   6 // 元素值
0   1   2   3   4   5   6   7   8 // 下标
  • 然后,创建一个新数组resultArr,长度和原数组arr一样。从后往前遍历原数组arr,第一个是5,标记是小白,count[5]的值是4,表示小白排第四位,所以resultArr[4-1] = 5,同时count[5]--,即把4变成3,下一个5就表示排第三位,小红就排第三,和原数组的顺序一致。这样一来,就将计数排序变成稳定的了。

3. 问题二:

假如现有待排序列arr如下:

999   998   1000  995

按照之前的说法,count数组的最大下标是arr数组最大值,即如果要排这四个数,需要创建长度为1001的数组。而且,下标0到994的这些空间都用不到,白白浪费了。所以,count数组的长度应该是max(arr) - min(arr) + 1,即用最大值减去最小值再加1即可。此案例中,count的长度就是1000 - 995 + 1 = 6,那么每个元素应该放在哪个下标上呢?每个元素都减去最小元素,得出来的值就对应count的下标。比如999 - 995 = 4,那么999就应该对应count[4]

4. 计数排序的缺点: 从上面的分析可以知道,计数排序适合分布比较集中的数据,即最大值和最小值相差不多,如果相差特别多,就会很耗费空间。

二、代码实现

public static void countSort(int[] arr) {
    if (arr == null || arr.length == 1) {
        return;
    }
    // 1. 找到数组中最大的数和最小的数
    int max = arr[0];
    int min = arr[0];
    for (int i=1; i<arr.length; i++) {
        max = arr[i] > max ? arr[i] : max;
        min = arr[i] < min ? arr[i] : min;
    }
    // 2. 定义count数组
    int[] count = new int[max - min + 1];
    // 3. 遍历原数组,进行计数
    for (int i=0; i<arr.length; i++) {
        count[arr[i] - min]++;
    }
    // 4. 对count数组进行变形,让计数排序变成稳定的
    for (int i=1; i<count.length; i++) {
        count[i] += count[i-1];
    }
    // 5. 创建接收结果的数组
    int[] result = new int[arr.length];
    // 6. 倒序遍历原数组,并且将结果存到result数组中
    for (int i=arr.length-1; i>=0; i--) {
        result[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min] --;
    }
    // 7. 把result数组拷贝回原数组即可
    System.arraycopy(result, 0, arr, 0,  arr.length);
}
下一篇
举报

扫码关注云+社区

领取腾讯云代金券