排序算法--计数排序
统计每个元素出现的次数,直接计算元素在有序序列中的位置,要求数据是整数且范围有限。适用于数据为小范围整数(如年龄、成绩),数据重复率较高时效率更优。可用于小范围整数排序、基数排序的底层排序(作为基数排序的稳定排序子过程)、统计频率分布(快速获取元素分布直方图)、海量数据预处理(配合外部排序处理大数据文件)
#include <stdlib.h>
#include <assert.h>// 计数排序核心函数(稳定排序版本)
void countingSort(int arr[], int n) {if (n <= 1) return; // 无需排序// 1. 确定数据范围int max = arr[0], min = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}const int range = max - min + 1; // 实际数值范围// 2. 创建计数数组并初始化int* count = (int*)calloc(range, sizeof(int));assert(count != NULL);// 3. 统计每个元素出现次数for (int i = 0; i < n; i++) {count[arr[i] - min]++; // 偏移处理负数}// 4. 计算累计位置(保证稳定性)for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 5. 反向填充结果数组(关键稳定性操作)int* output = (int*)malloc(n * sizeof(int));assert(output != NULL);for (int i = n - 1; i >= 0; i--) {output[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--;}// 6. 复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 7. 释放内存free(count);free(output);
}
#include <stdio.h>
// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {// 测试数据(包含负数)int arr[] = {-5, 2, -3, 4, 1, 2, 8, 5, 3, -1};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前: ");printArray(arr, n);countingSort(arr, n);printf("排序后: ");printArray(arr, n);return 0;
}
优化建议:
1.通过min值偏移处理负数,支持全整数范围排序
2.通过反向遍历填充输出数组,保留相同元素的原始顺序,已保证稳定性
3.动态计算range值,避免不必要的内存浪费
void countingSortSpaceOptimized(int arr[], int n) {// ...(省略范围计算步骤)...// 直接根据计数数组覆盖原数组(非稳定)int idx = 0;for (int i = 0; i < range; i++) {while (count[i]-- > 0) {arr[idx++] = i + min;}}
}
相关文章:
排序算法--计数排序
统计每个元素出现的次数,直接计算元素在有序序列中的位置,要求数据是整数且范围有限。适用于数据为小范围整数(如年龄、成绩),数据重复率较高时效率更优。可用于小范围整数排序、基数排序的底层排序(作为基数排序的稳定…...
[特殊字符]const在函数前后的作用详解(附经典案例)
理解const在函数前后的位置差异,是掌握C精髓的重要一步。下面用几个超形象的例子,带你彻底搞懂这个知识点! 情况1:const在函数后面(成员函数限定符) 作用:承诺这个成员函数不会修改对象的状态&…...
【字节青训营-7】:初探 Kitex 字节微服务框架(使用ETCD进行服务注册与发现)
本文目录 一、Kitex概述二、第一个Kitex应用三、IDL四、服务注册与发现 一、Kitex概述 长话短说,就是字节跳动内部的 Golang 微服务 RPC 框架,具有高性能、强可扩展的特点,在字节内部已广泛使用。 如果对微服务性能有要求,又希望…...
给AI用工具的能力——Agent
ReAct框架: Reason Action,推理与行动结合 可以借助思维链,用小样本提示展示给模型一个ReAct框架 推理:针对问题或上一步观察的思考 行动:基于推理,与外部环境的一些交互(调用外部工具&…...
Jupyter Lab的使用
Lab与Notebook的区别: Jupyter Lab和Jupyter notebook有什么区别,这里找到一篇博客不过我没细看, Jupyter Lab和Jupyter Notebook的区别 - codersgl - 博客园 使用起来Lab就是一个更齐全、功能更高级的notebook, 启用滚动输出: 有时候一个…...
【从零开始的LeetCode-算法】922. 按奇偶排序数组 II
给定一个非负整数数组 nums, nums 中一半整数是 奇数 ,一半整数是 偶数 。 对数组进行排序,以便当 nums[i] 为奇数时,i 也是 奇数 ;当 nums[i] 为偶数时, i 也是 偶数 。 你可以返回 任何满足上述条件的…...
RabbitMQ深度探索:前置知识
消息中间件: 消息中间件基于队列模式实现异步 / 同步传输数据作用:可以实现支撑高并发、异步解耦、流量削峰、降低耦合 传统的 HTTP 请求存在的缺点: HTTP 请求基于响应的模型,在高并发的情况下,客户端发送大量的请求…...
『 C++ 』中不可重写虚函数的实用案例
文章目录 框架设计:保障核心逻辑稳定避免误操作:防止逻辑混乱确保接口一致:库与API设计 在C编程里,用final关键字修饰、不允许被继承(重写)的虚函数其实很有用。接下来我就结合实际案例,给大家讲…...
Redis - String相关命令
目录 setgetmsetmgetsetnx、setex、psetexincr、incrby、decr、decrby、incrbyfloatappendgetrangesetrangestrlen字符串类型编码方式总结 Redis - String Redis存储的字符串,是直接按二进制方式存储,不会做任何编码转换,存的是什么ÿ…...
pytorch基于FastText实现词嵌入
FastText 是 Facebook AI Research 提出的 改进版 Word2Vec,可以: ✅ 利用 n-grams 处理未登录词 比 Word2Vec 更快、更准确 适用于中文等形态丰富的语言 完整的 PyTorch FastText 代码(基于中文语料),包含࿱…...
3D人脸建模:高精度3D人脸扫描设备快速生成真人脸部3D模型
什么是3D人脸建模? 3D人脸建模,即借助特定技术手段,获取人脸三维数据,并构建出能精准呈现人脸形状、纹理等特征的三维模型。这一技术广泛应用于计算机视觉、人机交互、虚拟现实、影视制作等多个领域,为各行业都带来了前所未有的创…...
4.PPT:日月潭景点介绍【18】
目录 NO1、2、3、4 NO5、6、7、8 NO9、10、11、12 表居中或者水平/垂直居中单元格内容居中或者水平/垂直居中 NO1、2、3、4 新建一个空白演示文稿,命名为“PPT.pptx”(“.pptx”为扩展名)新建幻灯片 开始→版式“PPT_素材.doc…...
冷链监控系统
前后端源码 wx :bright12389 冷链系统需求分析 1. 项目背景 冷链系统用于监控和管理冷链物流过程中的环境参数(如温度、湿度),确保货物在运输、存储过程中的质量安全。系统需支持实时监控、历史数据分析、异常告警等功能。 2.…...
VSCode中代码颜色异常
检查右下角语言模式是否是HTML, 如果不是就点击更改为HTML模式即可...
表格标签的使用
一.表格标签 1.1表格标签的作用 用来显示和展示数据,不是用来布局页面的。 1.2表格的基本语法 <table> //用于定义表格标签 <tr> // table row 用于定义表格中的行,必须嵌套在<table> </table>标签中 <td>单元格内的文…...
llama.cpp GGUF 模型格式
llama.cpp GGUF 模型格式 1. Specification1.1. GGUF Naming Convention (命名规则)1.1.1. Validating Above Naming Convention 1.2. File Structure 2. Standardized key-value pairs2.1. General2.1.1. Required2.1.2. General metadata2.1.3. Source metadata 2.2. LLM2.2.…...
嵌入式硬件篇---HAL库内外部时钟主频锁相环分频器
文章目录 前言第一部分:STM32-HAL库HAL库编程优势1.抽象层2.易于上手3.代码可读性4.跨平台性5.维护和升级6.中间件支持 劣势1.性能2.灵活性3.代码大小4.复杂性 直接寄存器操作编程优势1.性能2.灵活性3.代码大小4.学习深度 劣势1.复杂性2.可读性3.可维护性4.跨平台性…...
【IoCDI】_@Bean的参数传递
目录 1. 不创建参数类型的Bean 2. 创建一个与参数同类型同名的Bean 3. 创建多个与参数同类型,其中一个与参数同名的Bean 4. 创建一个与参数同类型不同名的Bean 5. 创建多个与参数同类型但不同名的Bean 对于Bean修饰的方法,也可能需要从外部传参&…...
[特殊字符] ChatGPT-4与4o大比拼
🔍 ChatGPT-4与ChatGPT-4o之间有何不同?让我们一探究竟! 🚀 性能与速度方面,GPT-4-turbo以其优化设计,提供了更快的响应速度和处理性能,非常适合需要即时反馈的应用场景。相比之下,G…...
【模型】Bi-LSTM模型详解
1. 模型架构与计算过程 Bi-LSTM 由两个LSTM层组成,一个是正向LSTM(从前到后处理序列),另一个是反向LSTM(从后到前处理序列)。每个LSTM单元都可以通过门控机制对序列的长期依赖进行建模。 1. 遗忘门 遗忘…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
