当前位置:网站首页>(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
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. 桶排序(附有自己的视频讲解)
边栏推荐
- 字节跳动面试题之镜像二叉树2020
- 顺序表删除所有值为e的元素
- APP product source data interface (taobao, jingdong/spelling/suning/trill platform details a lot data analysis interface) code and docking tutorial
- AD的library中 库文件后缀有.intlib .schlib .pcblib 的区别
- 2022-08-08: Given an array arr, it represents the height of the missiles that will appear in order from morning to night.When the cannon shoots missiles, once the cannon is set to shoot at a certain h
- Service
- idea中PlantUML插件使用
- MongDb的查询方式
- Common Oracle Commands
- AD picture PCB tutorial 20 minutes clear label shop operation process, copper network
猜你喜欢
随机推荐
Fragments
TCP段重组PDU
安装flask
e-learning summary
Thread Pool Summary
way of thinking problem-solving skills
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
6 states of a thread
先序遍历,中序遍历,后序遍历,层序遍历
Silently start over, the first page is also a new page
默默重新开始,第一页也是新的一页
找出数组中不重复的值php
Reverse Engineering
Explain the wait() function and waitpid() function in C language in detail
Flask failed to create database without error
APP product source data interface (taobao, jingdong/spelling/suning/trill platform details a lot data analysis interface) code and docking tutorial
makefile记录
XxlJobConfig分布式定时器任务管理XxlJob配置类,替代
cut命令的使用实例
P7阿里面试题2020.07 之滑动窗算法(阿里云面试)