【算法】计数排序算法的讲解和代码实践

思路

计数排序是三个桶排序算法之一(计数排序、基数排序、桶排序),是不需要通过比较就可以对数组进行排序的一种算法。
计数排序的主要思路是:
1、新建一个数组,数组长度为原数组中最大的元素 + 1;
2、遍历原数组,将新数组下标等于原数组当前元素的值 + 1,也就是计数了;
3、遍历新数组,按下标依次取出所有元素值不为0的所有下标,并且元素值为几就取几次;
4、全部取出来就是排好序的数组。
另外说明一下计数排序的适用场景:
1、因为是使用数组下标 = 原数组值的形式计数的,所有原数组中的元素只能是大于等于0的数;
2、数组中的元素间隔越小越好。比如如果有一个数组是[1, 2, 99999],这样的话,虽然只有3个元素,却需要创建一个100000大小的数组才能进行计数排序。

讲解

有数组如下:

image.png

我们先创建一个新的数组,长度为原数组中最大值 8 + 1:

image.png

然后开始遍历原数组,第一个数为 2,那么新数组下标 2 的值 + 1:

image.png

第二个元素为 0,新数组下标 0 的值 + 1:

image.png

以此类推,直到遍历完整个原数组,最终新数组如下:

image.png

这时候我们就可以遍历新数组,把所有下标取出,次数为下标对应的值。首先取出 0,0 对应的值为 1,取出一个即可:

image.png

1 也是同样的,只取出一个:

image.png

一直到下标 3 ,下标 3 的值为 2,需要取出两个:

image.png

后面的 4 和 7 下标对应的值为 0,不需要取。
直至取完所有元素,数组也就完成了排序:

image.png

实现

    @Test
    public void sortTest() {
        int[] nums = new int[]{2, 0, 1, 8, 3, 3, 6, 5};
        countSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private void countSort(int[] nums) {
        if (nums.length < 2) {
            return;
        }
        // 为了确定新数组大小,先找出原数组最大值
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
            }
        }
        // 定义新数组
        int[] result = new int[maxValue + 1];
        // 遍历原数组,将新数组下标对应的值 + 1
        for (int i = 0; i < nums.length; i++) {
            result[nums[i]] += 1;
        }
        // 将原数组作为结果数组,遍历并设值
        for (int i = 0, j = 0; i < nums.length;) {
            // 遍历新数组
            for (; j < result.length; j++) {
                // 遍历新数组中的某一个元素,遍历次数为该元素的值
                for (int k = 0; k < result[j]; k++) {
                    // 取出下标设置到结果数组中
                    nums[i] = j;
                    i++;
                }
            }
        }
    }

看下运行结果:

image.png

版权声明:
作者:lichengxin
链接:https://www.techfm.club/p/43597.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>