当前位置:网站首页>(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
2022-08-09 06:50:00 【学习追求高效率】
4. 其他非基于比较排序(了解)
1. 计数排序(附有自己的视频讲解)
计数排序
/** * 时间复杂度:O(N+范围) * 空间复杂度:O(范围) * 稳定性: * 计数排序:适合 给定一个范围的数据 进行排序 * @param array */
public static void countSort(int[] array) {
int maxVal = array[0];
int minVal = array[0];
for (int i = 0; i < array.length; i++) {
if(array[i] < minVal) {
minVal = array[i];
}
if(array[i] > maxVal) {
maxVal = array[i];
}
}
//就能确定当前数组的最大值 和 最小值
int len = maxVal - minVal + 1;
int[] count = new int[len];
//开始遍历array数组 进行计数
for (int i = 0; i < array.length; i++) {
int val = array[i];
count[val-minVal]++;
}
int index = 0;//array数组的下标
for (int i = 0; i < count.length; i++) {
//确保 当前count数组 可以检查完
while (count[i] != 0) {
array[index] = i+minVal;
index++;
count[i]--;
}
}
}
思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。 操作步骤
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
【计数排序的特性总结】
- 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
- 时间复杂度:O(MAX(N,范围))
- 空间复杂度:O(范围)
- 稳定性:稳定
2. 基数排序(附有自己的视频讲解)
基数排序+桶排序
3. 桶排序(附有自己的视频讲解)
边栏推荐
猜你喜欢
随机推荐
Common Oracle Commands
6 states of a thread
eyb:Redis学习(2)
Use baidu EasyDL intelligent bin
如何操作数据库
简单工厂模式
C语言的内置宏(定义日志宏)
高项 03 项目立项管理
2017.10.26模拟 b energy
pycharm环境包导入到另外一个环境
Example of using the cut command
C语言实现顺序栈和链队列
shardingsphere数据分片配置项说明和示例
95后,刚工作2-3年就年薪50W+ ,才发现打败我们的,从来不是年龄···
VS2019常用快捷键
mysql summary
【修电脑】系统重装但IP不变后VScode Remote SSH连接失败解决
【MySQL】update mysql.user set authentication_string=password(“123456“) where User=‘root‘; 报错
高项 04 项目变更管理
SIGINT, SIGKILL, SIGTERM signal difference, summary of various signals