计数排序 介绍
【十大排序|十大排序--计数排序】计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间(桶)中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。步骤
当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是O ( n + k ) O(n + k) O(n+k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组count的长度取决于待排序数组中数据的范围(等于待排序数组的最大值加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。
- 找出待排序的数组中的最小值和最大值;
- 统计数组中每个元素出现的次数,存入计数数组count;
- 按待排序数组最小值到最大值遍历计数桶;
- 将每个桶中的数据依次覆盖到原数组;
图片来源于:https://www.runoob.com/w3cnote/counting-sort.html
代码与思想
/**
* TODO 计数排序
* 思想:哈希表
* @author nanfeng
* @date 2022/03/19/ 16:01
*/
public class CountSort {
public static void main(String[] args) {
int[] nums = new int[]{711,42,333,6,7555,85,93,24,30,177};
countSort(nums);
System.out.println(Arrays.toString(nums));
}static void countSort(int[] nums) {
// 最大值、最小值赋初始值
int max = nums[0], min = nums[0];
// 计算出数组中得最大值
for (int num : nums) max = Math.max(num, max);
// 计算出数组中得最小值
for (int num : nums) min = Math.min(num, min);
// 记录出现次数得数组
int[] count = new int[max + 1];
// 根据数组元素出现次数进行计数
for (int num : nums) count[num]++;
// 待排序数组指针
int index = 0;
// 从小打到开始遍历,放置数据
for (int i = min;
i <= max;
i++) {
// 输出当前桶中 数据,原数组接收从小到大的桶中数据
while (count[i]-- > 0) nums[index++] = i;
}
}
}
推荐阅读
- 数据库|从 SQL Server 到 MySQL (一)(异构数据库迁移)
- mysql|7、mysql的redo log、bin log日志
- java项目精品实战案例|基于Java+SpringBoot+vue+element实现前后端分离蛋糕商城系统详细设计
- 数据库|教你用 docker 搞个网站
- #|轮廓阴影和圆角
- HTML|HTML 向右侧展开div
- 我想谈一谈外包,请不要“妖魔化”它。
- Java基础|10 继承、super、this、抽象类
- java|java-继承,super关键字,this关键字,抽象方法和抽象类,红包案例分析实现