【java实现+4种变体完整例子】排序算法中【计数排序】的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格
以下是计数排序的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格:
一、计数排序基础实现
原理
通过统计每个元素的出现次数,按顺序累加得到每个元素的最终位置,并填充到结果数组中。
代码示例
public class CountingSort {void sort(int[] arr) {if (arr.length == 0) return;// 找到数据范围int min = Arrays.stream(arr).min().getAsInt();int max = Arrays.stream(arr).max().getAsInt();int range = max - min + 1;// 统计每个元素出现的次数int[] count = new int[range];for (int num : arr) {count[num - min]++;}// 累加统计结果,得到每个元素的最终位置for (int i = 1; i < count.length; i++) {count[i] += count[i - 1];}// 反向填充结果数组以保持稳定性int[] output = new int[arr.length];for (int i = arr.length - 1; i >= 0; i--) {int num = arr[i];output[count[num - min] - 1] = num;count[num - min]--;}// 将结果复制回原数组System.arraycopy(output, 0, arr, 0, arr.length);}
}
复杂度分析
- 时间复杂度:
O(n + k)
(n
为元素数量,k
为值域范围)。 - 空间复杂度:
O(k)
。 - 稳定性:稳定(相同值的元素相对顺序不变)。
二、常见变体及代码示例
1. 支持负数的计数排序
改进点:通过偏移量处理负数,扩展适用范围。
适用场景:数据包含负值。
public class CountingSortWithNegatives {void sort(int[] arr) {if (arr.length == 0) return;int min = Arrays.stream(arr).min().getAsInt();int max = Arrays.stream(arr).max().getAsInt();int range = max - min + 1;int[] count = new int[range];for (int num : arr) {count[num - min]++; // 偏移量为min}for (int i = 1; i < count.length; i++) {count[i] += count[i - 1];}int[] output = new int[arr.length];for (int i = arr.length - 1; i >= 0; i--) {int num = arr[i];output[count[num - min] - 1] = num;count[num - min]--;}System.arraycopy(output, 0, arr, 0, arr.length);}
}
2. 原地计数排序
改进点:尝试在原数组上操作,减少额外空间。
适用场景:内存受限场景(但可能牺牲时间效率)。
public class InPlaceCountingSort {void sort(int[] arr) {if (arr.length == 0) return;int min = Arrays.stream(arr).min().getAsInt();int max = Arrays.stream(arr).max().getAsInt();int range = max - min + 1;int[] count = new int[range];for (int num : arr) {count[num - min]++;}// 直接在原数组上填充int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {arr[index++] = i + min;count[i]--;}}}
}
3. 并行计数排序
改进点:利用多线程加速计数统计。
适用场景:超大数据集或并行计算环境。
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;public class ParallelCountingSort {void sort(int[] arr) {if (arr.length == 0) return;int min = Arrays.stream(arr).min().getAsInt();int max = Arrays.stream(arr).max().getAsInt();int range = max - min + 1;int[] count = new int[range];// 并行统计ForkJoinPool pool = new ForkJoinPool();pool.invoke(new CountTask(arr, count, 0, arr.length - 1, min));// 累加统计结果for (int i = 1; i < count.length; i++) {count[i] += count[i - 1];}int[] output = new int[arr.length];for (int i = arr.length - 1; i >= 0; i--) {int num = arr[i];output[count[num - min] - 1] = num;count[num - min]--;}System.arraycopy(output, 0, arr, 0, arr.length);}// 并行统计任务private static class CountTask extends RecursiveAction {private final int[] arr;private final int[] count;private final int start;private final int end;private final int min;CountTask(int[] arr, int[] count, int start, int end, int min) {this.arr = arr;this.count = count;this.start = start;this.end = end;this.min = min;}@Overrideprotected void compute() {if (end - start < 1000) { // 小区间直接统计for (int i = start; i <= end; i++) {count[arr[i] - min]++;}} else {int mid = (start + end) / 2;invokeAll(new CountTask(arr, count, start, mid, min),new CountTask(arr, count, mid + 1, end, min));}}}
}
三、变体对比表格
变体名称 | 时间复杂度 | 空间复杂度 | 稳定性 | 主要特点 | 适用场景 |
---|---|---|---|---|---|
基础计数排序 | O(n + k) | O(k) | 稳定 | 简单易实现,适用于小范围数据 | 值域较小且无负数的场景 |
支持负数的计数排序 | O(n + k) | O(k) | 稳定 | 扩展支持负数,需计算最小值 | 数据包含负值的场景 |
原地计数排序 | O(n + k) | O(k) | 稳定 | 减少输出数组的使用,直接修改原数组 | 内存受限但时间允许的场景 |
并行计数排序 | O(n/k + k) (并行) | O(k) | 稳定 | 利用多线程加速统计步骤 | 超大数据集或高性能计算环境 |
四、关键选择原则
- 基础场景:优先使用基础计数排序,因其简单且适用于小范围数据。
- 负数支持:当数据包含负值时,需使用支持负数的变体。
- 内存限制:原地排序适合内存紧张但允许额外统计数组的场景。
- 性能优化:并行计数排序适用于超大数据集或并行计算环境。
- 稳定性需求:所有变体均稳定,适用于需保持元素相对顺序的场景(如排序带键值的记录)。
通过选择合适的变体,可在特定场景下优化性能或扩展适用性。例如,并行计数排序在大数据集上显著提升速度,而支持负数的变体扩展了算法的通用性。
相关文章:
【java实现+4种变体完整例子】排序算法中【计数排序】的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格
以下是计数排序的详细解析,包含基础实现、常见变体的完整代码示例,以及各变体的对比表格: 一、计数排序基础实现 原理 通过统计每个元素的出现次数,按顺序累加得到每个元素的最终位置,并填充到结果数组中。 代码示…...
Qt C++ 解析和处理 XML 文件示例
使用 Qt C 解析和处理 XML 文件 以下是使用 Qt C 实现 XML 文件处理的几种方法,包括解析、创建和修改 XML 文件。 1. 使用 QXmlStreamReader (推荐方式) #include <QFile> #include <QXmlStreamReader> #include <QDebug>void parseXmlWithStr…...
在服务器上部署MinIO Server
MinIO的优势 高性能:MinIO号称是目前速度最快的对象存储服务器,据称在标准硬件上,对象存储的读/写速度最高可以高达183 GB/s和171 GB/s,可惜我的磁盘跟不上 兼容性:MinIO基于Amazon S3协议,并提供了与S3兼…...
第二十七讲:AI+农学导论
关键词:人工智能、农业、作物识别、遥感、机器学习、案例实战 目录 📌 一、为什么农业需要人工智能? 📈 二、AI在农学中的典型应用场景 🧪 三、实战案例:AI识别作物类型(以随机森林为例) ✅ 数据集:iris(模拟作物种类识别) 📦 所需包: 🚀 数据准备: …...
医院科研科AI智能科研支撑平台系统设计架构方案探析
一、系统设计概述 1.1 系统定位 本系统是基于MCP(Model Context Protocol,模型上下文协议)协议构建的智能科研支撑平台,旨在为医院科研科室提供全流程AI辅助能力,覆盖课题立项、数据采集、分析建模到成果转化的完整科研生命周期。系统通过MCP协议实现与医院信息系统的深…...
Python基础总结(七)之条件语句
文章目录 条件语句if一、Python中的真假二、条件语句格式2.1 if语句格式2.2 if-else语句2.3 if-elif-else语句 三、if语句嵌套 条件语句if 条件语句其实就是if语句,在讲解if语句之前需要知道Python中对于真假的判断。 一、Python中的真假 在Python中非0的都为真&…...
Day10【基于encoder- decoder架构实现新闻文本摘要的提取】
实现新闻文本摘要的提取 1. 概述与背景2.参数配置3.数据准备4.数据加载5.主程序6.预测评估7.生成效果8.总结 1. 概述与背景 新闻摘要生成是自然语言处理(NLP)中的一个重要任务,其目标是自动从长篇的新闻文章中提取出简洁、准确的摘要。近年来…...
深度解析算法之二分查找(2)
17.二分查找 题目链接 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target…...
前端工程化之自动化测试
自动化测试 自动化测试为什么需要测试?什么时候需要考虑测试测试类型前端测试框架单元测试Jest 重点掌握项目示例package.jsonsrc/utils/math.tssrc/utils/math.test.ts进行测试jest.config.js覆盖率直观看覆盖率coverage/lcov-report/index.html src/main.test.tst…...
CANFD技术在新能源汽车通信网络中的应用与可靠性分析
一、引言 新能源汽车产业正处于快速发展阶段,其电子系统复杂度不断攀升,涵盖众多传感器、控制器与执行器。高效通信网络成为确保新能源汽车安全运行与智能功能实现的核心要素。传统CAN总线因带宽限制,难以满足高级驾驶辅助系统(A…...
【机器学习】朴素贝叶斯算法:原理剖析与实战应用
引言 朴素贝叶斯算法就像是一位善于从经验中学习的侦探,根据已有的线索来推断未知事件的概率。这是一种基于概率论的分类算法,以贝叶斯定理为基础,却做了一个"朴素"的假设:认为所有特征彼此独立。虽然这个假设在现实中…...
【更新完毕】2025妈妈杯C题 mathercup数学建模挑战赛C题数学建模思路代码文章教学:音频文件的高质量读写与去噪优化
完整内容请看文章最下面的推广群 我将先给出文章、代码、结果的完整展示, 再给出四个问题详细的模型 面向音频质量优化与存储效率提升的自适应编码与去噪模型研究 摘 要 随着数字媒体技术的迅速发展,音频处理技术在信息时代的应用愈加广泛,特别是在存储…...
UI键盘操作
1、Selenium中send_keys除了可以模拟键盘输入之外,还有些时候需要操作键盘上的按键,甚至是组合键,比如CTRLA,CTRLC等, 所以我们需要代码操作键盘。使用的是send_keys里的Keys的类。 from selenium.webdriver.common.keys import …...
【正则表达式】正则表达式使用总结
正则表达式除了匹配普通字符外,还可以匹配特殊字符,这些特殊字符被称为“元字符”。 特殊字符(元字符) 限定符:用于指定正则表达式中某个组件的出现次数。常见的限定符包括: *:0次或多次 +:1次或多次 ?:0次或1次 {n}:恰好n次…...
Qt编写推流程序/支持webrtc265/从此不用再转码/打开新世界的大门
一、前言 在推流领域,尤其是监控行业,现在主流设备基本上都是265格式的视频流,想要在网页上直接显示监控流,之前的方案是,要么转成hls,要么魔改支持265格式的flv,要么265转成264,如…...
Spring Boot 中基于 Reactor 的服务器端事件(SSE)推送机制实践
Spring Boot 3.0 中基于 Reactor 的服务器端事件(SSE)推送机制实践 在现代 Web 应用开发中,实时数据交互越来越成为刚需,从股票行情的实时更新到社交平台的消息即时推送,服务器端事件(Server-Sent Events,简称 SSE)作为一种高效的单向数据传输技术,正发挥着重要作用。…...
CRC实战宝典:从原理到代码,全面攻克循环冗余校验
CRC实战宝典:从原理到代码,全面攻克循环冗余校验 github开源:CRC软硬件协同测试项目 CRC 简介 CRC(循环冗余校验)是一种强大的错误检测技术,广泛应用于数字网络和存储系统。它是确保数据完整性的重要方法…...
【愚公系列】《Python网络爬虫从入门到精通》056-Scrapy_Redis分布式爬虫(Scrapy-Redis 模块)
🌟【技术大咖愚公搬代码:全栈专家的成长之路,你关注的宝藏博主在这里!】🌟 📣开发者圈持续输出高质量干货的"愚公精神"践行者——全网百万开发者都在追更的顶级技术博主! …...
ZLMediaKit 和 SRS的区别,哪个更好用?
ZLMediaKit 和 SRS(Simple RTMP Server)是两个主流的开源流媒体服务器框架,各自在功能、性能、适用场景等方面存在显著差异。以下是两者的对比分析及选择建议: 一、核心差异对比 协议支持 ZLMediaKit:支持更广泛的流媒…...
【PyTorch】colab上跑VGG(深度学习)数据集是 CIFAR10
跑得结果是测试准确率10%,欠拟合。 import torch import torchvision.datasets from torch import nn from torch.utils.data import DataLoader from torch.utils.tensorboard import SummaryWriter from torchvision import datasets, transformstransform tran…...
pytorch 51 GroundingDINO模型导出tensorrt并使用c++进行部署,53ms一张图
本专栏博客第49篇文章分享了将 GroundingDINO模型导出onnx并使用c++进行部署,并尝试将onnx模型转换为trt模型,fp16进行推理,可以发现推理速度提升了一倍。为此对GroundingDINO的trt推理进行调研,发现 在GroundingDINO-TensorRT-and-ONNX-Inference项目中分享了模型导出onnx…...
编程语言基础 - C++ 面试题
C++ 面试题 tags: c++ 文章目录 C++ 面试题关键字1. const2. static3. this 指针4. inline 内联函数5. volatile6. struct, class7. enum关键字 1. const 修饰变量:该变量不能被改变 修饰指针: 指针常量: 指针本身是常量 TYPE* const pContent;指向常量的指针:指针所指向…...
JVM笔记【一】java和Tomcat类加载机制
JVM笔记一java和Tomcat类加载机制 java和Tomcat类加载机制 Java类加载 * loadClass加载步骤类加载机制类加载器初始化过程双亲委派机制全盘负责委托机制类关系图自定义类加载器打破双亲委派机制 Tomcat类加载器 * 为了解决以上问题,tomcat是如何实现类加载机制的…...
Python----深度学习(全连接与链式求导法则)
一、机器学习和深度学习的区别 机器学习:利用计算机、概率论、统计学等知识,输入数据,让计算机学会新知 识。机器学习的过程,就是训练数据去优化目标函数。 深度学习:是一种特殊的机器学习,具有强大的能力和…...
基于SpringBoot的网上找律师管理系统
博主介绍:java高级开发,从事互联网行业六年,熟悉各种主流语言,精通java、python、php、爬虫、web开发,已经做了六年的毕业设计程序开发,开发过上千套毕业设计程序,没有什么华丽的语言࿰…...
《目标检测双雄:YOLO与Faster R-CNN,谁主沉浮?》
在计算机视觉的广阔天地里,目标检测技术宛如一颗璀璨的明星,照亮了无数应用场景。从安防监控中对行人与车辆的精准识别,到自动驾驶领域对道路障碍物的快速判断,再到工业生产里对产品缺陷的严格检测,目标检测无处不在&a…...
CUDA编程中影响性能的小细节总结
一、内存访问优化 合并内存访问:确保相邻线程访问连续内存地址(全局内存对齐访问)。优先使用共享内存(Shared Memory)减少全局内存访问。避免共享内存的Bank Conflict(例如,使用padding或调整访…...
C#学习第17天:序列化和反序列化
什么是序列化? 定义:序列化是指把对象转换为一种可以轻松存储或传输的格式,如JSON、XML或二进制格式。这个过程需要捕获对象的类型信息和数据内容。用途:使得对象可以持久化到文件、发送至网络、或存储在数据库中。 什么是反序列…...
kafka的零拷贝技术
在 Kafka 中,高性能数据传输依赖于操作系统提供的 零拷贝(Zero-Copy) 技术,主要包括 sendfile 和 mmap 两种实现方式。它们的核心目标是减少数据在用户态和内核态之间的拷贝次数,从而提升 I/O 效率。下面详细解析它们的…...
从 0~1 保姆级 详细版 PostgreSQL 数据库安装教程
PostgreSQL数据库安装 PostgreSQL官网 【PostgreSQL官网】 | 【PostgreSQL安装官网_Windows】 安装步骤 step1: 选择与电脑相对应的PostgreSQL版本进行下载。 step2: 双击打开刚才下载好的文件。 step3: 在弹出的setup窗口中点击 …...
MySQL中常用函数的分类及示例
概述 以下是 MySQL 中常用函数的分类及示例,涵盖字符串处理、数值计算、日期操作、条件判断等常见场景: 一、字符串函数 1. CONCAT(str1, str2, ...) 拼接字符串。 SELECT CONCAT(Hello, , World); -- 输出: Hello World2. SUBSTRING(str, start,…...
【论文阅读21】-PSOSVM-CNN-GRU-Attention-滑坡预测(2024-12)
这篇论文主要提出并验证了一种新型的混合智能模型(PSOSVM-CNN-GRU-Attention),用于准确预测滑坡的点位移,并构建可靠的位移预测区间。通过对Baishuihe滑坡和Shuping滑坡的案例分析,展示了该模型的出色性能。 [1] Zai D…...
Shiro-550 动调分析与密钥正确性判断
一、Shiro 简介 Apache Shiro是一个开源安全框架,用于构建 Java 应用程序,提供身份验证、授权、加密和会话管理等功能。 二、Shiro-550(CVE-2016-4437) 1、漏洞原理 Shiro 在用户登陆时提供可选项 RememberMe,若勾选…...
Codeforces Educational Round 177 Div. 2 【B题,C待补
B 二分 题意 样例 5 3 10 3 4 2 1 512 找最右边的L下标即可 思路 二分最靠右的L端点,R端点取最右端(n*k处),找到后,答案就是L的位置(pos),(因为如果pos满足,则pos左边的所有下标都满足 代码 const in…...
【Lua语言】Lua语言快速入门
初始Lua Lua是一种轻量小巧的脚本语言,他使用标准C语言编写并以源代码形式开放。这意味着Lua虚拟机可以很方便的嵌入别的程序中,从而为应用程序提供灵活的扩展和定制功能。同时,在目前脚本引擎中,Lua的运行速度占有绝对优势。 变…...
Matlab画海洋与大气变量的时间序列并带标记面的三维折线图--来源粉丝
Matlab画带标记面的三维折线图–来源粉丝 图片 目标图: 图片 复现: 图片 细节可在代码中更改: 数据构造 clear;clc;close all; % 数据构造 X1 1:8;Y1ones(length(X1),1); X2 X1;Y22*ones(length(X1),1); X3 X1;Y33*ones(length(X1),1); …...
NestJS——多环境配置方案(dotenv、config、@nestjs/config、joi配置校验)
个人简介 👀个人主页: 前端杂货铺 🙋♂️学习方向: 主攻前端方向,正逐渐往全干发展 📃个人状态: 研发工程师,现效力于中国工业软件事业 🚀人生格言: 积跬步…...
RAGFlow在Docker中运行Ollama直接运行于主机的基础URL的地址
基础Url http://host.docker.internal:11434...
python 库 下载 ,整合在一个小程序 UIUIUI
上图 import os import time import threading import requests import subprocess import importlib import tkinter as tk from tkinter import ttk, messagebox, scrolledtext from concurrent.futures import ThreadPoolExecutor, as_completed from urllib.parse import…...
【MySQL】数据库约束
个人主页:♡喜欢做梦 欢迎 👍点赞 ➕关注 ❤️收藏 💬评论 目录 ✨一、数据库的约束 🌟二、数据库约束的分类 🌍 1.非空约束(NOT NULL) 1.定义 2.格式 3.示例: 列的信息可…...
Firewalld防火墙
目录 Firewald 防火墙概述 Firewalld 简介 firewalld 与 iptables service的区别 Firewalld 网络区域 Firewalld 防火墙图形配置方法 服务选项 端口号 协议选项 源端口选项 伪装选项 端口转发 ICMP过滤器 防火墙的配置运行状态 运行时和永久有什么区别 Firewalld 防火墙 firewa…...
使用 TensorFlow 和 Keras 构建 U-Net
U-Net是图像分割领域中最为著名的架构之一。U-Net 因其形状而得名,它是一种全卷积架构,首先将图像收缩,然后将其扩展为输出结果。虽然这种收缩路径构建了一个学习特征的层次结构,但跳过连接有助于在扩展路径中将这些特征转换回相关…...
【网络篇】TCP vs UDP底层区别+网络编程概念
大家好呀 我是浪前 今天讲解的是网络篇的第三章:网络编程概念和TCP&UDP的区别 网络编程概念TCP和UDP的区别 跨主机通信:网络编程插座:网络编程的本质: 网络编程的重要概念:客户端和服务器: 客户端和服务器的交互模…...
如何保存服务器mysql数据库的数据到本地文件
打开mysql命令行如图1 图1 mysql命令行 修改文件保存路径。 在mysql安装目录下,找到my.ini文件,找到secure-file-priv变量配置的地方,修改对应的值,然后重启mysql,此时把文件放到指定路径,再执行导入导出…...
Flutter学习 滚动组件(2):ListView进阶使用
目录 前言:一、实现复杂的ListView列表:1.1 Item布局封装1.2 ListView的使用1.3 增加分割线 二、实现ListView下拉刷新:三、实现上拉加载更多:四、实现下拉刷新、上拉加载更多:五、ListView滚动方向和控制:…...
linux oracle 19c 静默安装
oracle数据库有个比较很抓瞎的事情,不同的版本搭建的大致流程是一样的,但是在实操细节上会有不同,比如操作的脚本位置和配置项等等,这些会变,所以需要时常积累不同版本的文档 这里有一点要说明,之所以使用…...
中间件--ClickHouse-11--部署示例(Linux宿主机部署,Docker容器部署)
一、Linux宿主机部署 1、环境准备 操作系统:推荐使用 CentOS 7/8 或 Ubuntu 18.04/20.04。硬件要求: 至少 2 核 CPU 和 4GB 内存。足够的磁盘空间(根据数据量评估)。CPU需支持SSE4.2指令集(可通过以下命令检查&#…...
AI调试工具有哪些?
一、深度学习框架专用调试工具 TensorBoard • 功能:实时监控训练指标(损失值、准确率)、可视化神经网络结构、分析参数分布和梯度信息 • 适用框架:TensorFlow、PyTorch(通过插件) • 特点:支持…...
Warcraft Logs [Classic] [WCL] BOSS ID query
Warcraft Logs [Classic] [WCL] BOSS ID query 所有副本BOSSID查询 https://wowpedia.fandom.com/wiki/DungeonEncounterID#Retail IDNameMapInstanceIDPatch227High Interrogator GerstahnBlackrock Depths230228Lord RoccorBlackrock Depths230229Houndmaster GrebmarBlackro…...
MySQL——事务
一、什么是事务? 事务(Transaction) 是数据库操作的最小逻辑单元,它由一组不可分割的SQL操作组成。事务的核心目标是确保多个操作要么全部成功,要么全部失败,从而维护数据的完整性。例如,银行转…...