【算法】计数排序算法的讲解和代码实践
思路
计数排序是三个桶排序算法之一(计数排序、基数排序、桶排序),是不需要通过比较就可以对数组进行排序的一种算法。
计数排序的主要思路是:
1、新建一个数组,数组长度为原数组中最大的元素 + 1;
2、遍历原数组,将新数组下标等于原数组当前元素的值 + 1,也就是计数了;
3、遍历新数组,按下标依次取出所有元素值不为0的所有下标,并且元素值为几就取几次;
4、全部取出来就是排好序的数组。
另外说明一下计数排序的适用场景:
1、因为是使用数组下标 = 原数组值的形式计数的,所有原数组中的元素只能是大于等于0的数;
2、数组中的元素间隔越小越好。比如如果有一个数组是[1, 2, 99999],这样的话,虽然只有3个元素,却需要创建一个100000大小的数组才能进行计数排序。
讲解
有数组如下:
我们先创建一个新的数组,长度为原数组中最大值 8 + 1:
然后开始遍历原数组,第一个数为 2,那么新数组下标 2 的值 + 1:
第二个元素为 0,新数组下标 0 的值 + 1:
以此类推,直到遍历完整个原数组,最终新数组如下:
这时候我们就可以遍历新数组,把所有下标取出,次数为下标对应的值。首先取出 0,0 对应的值为 1,取出一个即可:
1 也是同样的,只取出一个:
一直到下标 3 ,下标 3 的值为 2,需要取出两个:
后面的 4 和 7 下标对应的值为 0,不需要取。
直至取完所有元素,数组也就完成了排序:
实现
@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++;
}
}
}
}
看下运行结果:
版权声明:
作者:lichengxin
链接:https://www.techfm.club/p/43597.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。
共有 0 条评论