当前位置:网站首页>(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
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. 桶排序(附有自己的视频讲解)
边栏推荐
猜你喜欢
install flask
Go lang1.18入门精炼教程——第一章:环境搭建
db.sqlite3 has no "as Data Source" workaround
Import the pycharm environment package into another environment
e-learning summary
力扣第 305 场周赛复盘
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
The solution that does not work and does not take effect after VScode installs ESlint
分布式事务产生的原因
longest substring without repeating characters
随机推荐
The singleton pattern
多米诺骨牌
P7 Alibaba Interview Questions 2020.07 Sliding Window Algorithm (Alibaba Cloud Interview)
代码目录结构
Redis 2 - 高级
常用Oracle命令
字节也开始缩招了...
字节跳动面试题之镜像二叉树2020
Thread Pool Summary
APP商品详情源数据接口(淘宝/京东/拼多多/苏宁/抖音等平台详情数据分析接口)代码对接教程
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
【MySQL】update mysql.user set authentication_string=password(“123456“) where User=‘root‘; 报错
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
买口罩(0-1背包)
P7阿里面试题2020.07 之滑动窗算法(阿里云面试)
Fragments
数据库中间件-jdbi
Transaction concluded
默默重新开始,第一页也是新的一页
【修电脑】系统重装但IP不变后VScode Remote SSH连接失败解决