当前位置:网站首页>(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
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. 桶排序(附有自己的视频讲解)
边栏推荐
- io.lettuce.core。RedisCommandTimeoutException命令超时
- 95后,刚工作2-3年就年薪50W+ ,才发现打败我们的,从来不是年龄···
- Singleton DCL (double check the lock) full han mode and the hungry
- MongDb的查询方式
- 力扣 636. 函数的独占时间
- flask创建数据库失败未报错
- 6 states of a thread
- shardingsphere data sharding configuration item description and example
- 推进产教融合 赋能教育创新发展 | 华云数据荣获“企业贡献奖”
- AD画PCB板教程 20分钟讲清楚操作流程 铺铜 网络标号
猜你喜欢
随机推荐
【Docker】Docker安装MySQL
Fragments
Teach you how to make the Tanabata meteor shower in C language - elegant and timeless (detailed tutorial)
变压器的工作原理(图解,原理图讲解,一看就懂)
flask创建数据库失败未报错
详解C语言中的wait()函数和waitpid()函数
TCP段重组PDU
2017.10.26模拟 b energy
细谈VR全景:数字营销时代的宠儿
ByteDance Interview Questions: Mirror Binary Tree 2020
报错:flask: TypeError: ‘function‘ object is not iterable
APP商品详情源数据接口(淘宝/京东/拼多多/苏宁/抖音等平台详情数据分析接口)代码对接教程
Inception V3 Eye Closure Detection
高项 03 项目立项管理
分布式理论
长沙学院2022暑假训练赛(一)六级阅读
eyb:Redis学习(2)
Quectel EC20 4G module dial related
Introduction and use of BeautifulSoup4
VS2019常用快捷键