排序算法9----计数排序(C)

news/2024/2/23 13:56:08/文章来源:https://blog.csdn.net/2302_80873119/article/details/135597923

        计数排序是一种非比较排序,不比较大小 。

        1、思想

        计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。 

        2、步骤       

        1、统计数据:统计每个数据出现了多少次。(建立一个count数组,范围从[MIN,MAX],MAX代表arr中最大的一个数,MIN对应arr中最小的一个数,然后for循环遍历arr,出现一个数,就在count中对应位置++)。这叫count和arr相对映射。(相对最小值和最大值来开count的范围)

        2、用count覆盖arr: 因为count的下标代表arr中的数据值,count的内容代表出现的次数。

27b2c9cc31c94a23bc6a5ace24773f9a.png

 

        3、效率极高

        特点时间复杂度:O(aN+countN(范围)),即O( MAX {N,范围} )

               空间复杂度: O(范围)

        局限性:1、不适合分散的数据,更适合比较集中连续的数据。

                       2、不适合浮点数、字符串、结构体数据排序。,只适合整数(包括负数),因为count和arr是相对映射。

        4、代码

void CountingSort_incline(int*arr,int n)
{//找范围int min = arr[0], max = arr[0];for (int i = 0; i < n; i++){if (arr[i] < min)min = arr[i];if (arr[i] > max)max = arr[i];}int range = max - min + 1;//开count数组int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail\n");exit(-1);}//统计次数for (int i = 0; i < n; i++){count[arr[i] - min]++;//相对位置++,不是绝对位置}//count“覆盖”回去arrint i = 0;for (int j = 0; j < range; j++){while (count[j]--)//即看下标(相对数)出现了几次,就覆盖回去几次{arr[i++] = j+min;//j+min代表还原,即从相对位置得到原来的绝对值}}/*	例如:{-1,1,3,2,1,5,1,6};min = -1,max = 6;count[8];则每个数的相对值为arr[i] - min = arr[i] + 1;得到相对{0,2,4,3,2,6,2,7}
所以:count(下标出现次数):1  0  3  1  1  0  1  1相对下标:0  1  2  3  4  5  6  7下标还得到原数组元素的绝对值(下标 + min):{ -1,0,1,2,3,4,5,6 },分别对应次数{1,0,3,1,1,0,1,1};则覆盖回去arr数组:{-1,1,1,1,2,3,5,6};*/
}

        5、实现效果

	int arr[] = { 1,3,10,2,1,3,1,5,11,-2 };int size = sizeof(arr) / sizeof(int);printf("原数组\n");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}printf("\n");printf("排序后\n");CountingSort_incline(arr,size);for (int i = 0; i < size; i++){printf("%d ", arr[i]);}printf("\n");

原数组:1,3,10,2,1,3,1,5,11,-2

排序后:-2,1,1,1,2,3,3,5,10,11

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_926206.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

网页屏幕适配通透了

一&#xff0c;如果设计尺寸固定 那就按照固定尺寸开发 一般都是1920*1080 二&#xff0c;需要适配多种像素屏幕&#xff08;大屏可视化&#xff09; 可使用媒体查询设置多套css样式或者使用自适应单位&#xff0c;%&#xff0c;vw&#xff0c;vh 最好解决方案rem&#xff…

Unity Shader 的模板测试效果

模板测试是渲染管线中逐片元操作的一环&#xff0c;它的作用是筛选出指定模板的片元&#xff0c;而不符合模板的片元会被舍弃&#xff0c;从而做到一个遮罩的效果。 以下是Unity中实践的一个效果&#xff1a; 场景中可以看出&#xff0c;熊模型和茶壶模型都在差不多的位置&am…

Kafka 的架构

实验过程 1.三个虚拟机中解压kafka软件包 tar -zxvf kafka_2.11-1.1.1.tgz 2.修改 3 个节点配置文件 在 zookeeper 节点&#xff0c;进入 kafka_2.11-1.1.1/config 目录下&#xff0c;编辑 server.properties 文件 [rootdb1 ~]# cd kafka_2.11-1.1.1/config [rootdb1 con…

HarmonyOS应用开发者高级认证试题库(鸿蒙)

目录 考试链接&#xff1a; 流程&#xff1a; 选择&#xff1a; 判断 单选 多选 考试链接&#xff1a; 华为开发者学堂华为开发者学堂https://developer.huawei.com/consumer/cn/training/dev-certification/a617e0d3bc144624864a04edb951f6c4 流程&#xff1a; 先进行…

【一】通信协议概述

通信协议概述 简介&#xff1a; 很早之前就思考了要写一下电力系统常用的几种通信协议&#xff0c;一直拖着也没有行动&#xff0c;这次终于下定决心来出一个《通信协议》这样的专栏。电力行业数字化方面资料较少&#xff0c;我理解主要一方面是数字化程度还不高&#xff0c;一…

使用Python操纵Word自动编写离职报告

目录 一、背景介绍 二、技术原理 三、实现步骤 1、安装python-docx库 2、创建Word文档 3、添加标题和内容 4、添加表格和图片 5、设置样式和格式化文本 6、保存文档 四、注意事项与建议 总结 随着现代社会的发展&#xff0c;自动化和智能化已经成为各行各业追求的目…

使用PyTorch实现混合专家(MoE)模型

Mixtral 8x7B 的推出在开放 AI 领域引发了广泛关注&#xff0c;特别是混合专家&#xff08;Mixture-of-Experts&#xff1a;MoEs&#xff09;这一概念被大家所认知。混合专家(MoE)概念是协作智能的象征&#xff0c;体现了“整体大于部分之和”的说法。MoE模型汇集了各种专家模型…

消息的发送与接收

消息的发送与接收 消息的发送与接收不仅仅是在于聊天功能的实现。其实还有很多种情况也算"消息的发送与接收"。而且我们还可以通过多种方法去实现。我们可以基于实际情况来选择。 WebSocket实现 node做后端。找了好多&#xff0c;前端页面总是用到了jQuery&#x…

(C语言)冒泡排序

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>//实现buble_sort函数&#xff1b; void buble_sort(int arr[], int sz) {//初始化变量值&#xff1b;int i 0;//嵌套循环冒泡排序&#xff1b;//外层循环&…

【REST2SQL】10 REST2SQL操作指南

【REST2SQL】01RDB关系型数据库REST初设计 【REST2SQL】02 GO连接Oracle数据库 【REST2SQL】03 GO读取JSON文件 【REST2SQL】04 REST2SQL第一版Oracle版实现 【REST2SQL】05 GO 操作 达梦 数据库 【REST2SQL】06 GO 跨包接口重构代码 【REST2SQL】07 GO 操作 Mysql 数据库 【RE…

微信小程序-----全局配置与页面配置

目录 前言 全局配置文件 一、window 1. 小程序窗口的组成部分 2. window 节点常用的配置项 3. 设置导航栏的标题 4. 设置导航栏的背景色 5. 设置导航栏的标题颜色 6. 全局开启下拉刷新功能 7. 设置下拉刷新时窗口的背景色 8. 设置下拉刷新时 loading 的样式 9. 设置…

两步解决宝塔面板无法访问(无法访问或拒绝链接)

宝塔面板&#xff0c;突然无法进入&#xff0c;显示“IP拒绝链接”。 使用SSH工具登录服务器 /etc/init.d/bt defaultbt default 命令 宝塔获取登录的默认地址、用户名和登录密码&#xff1b; 重启面板服务 sudo /etc/init.d/bt初始化宝塔选项 漏刻有时

装饰者模式:打破继承限制,实现灵活的功能扩展

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 装饰者模式&#xff1a;打破继承限制&#xff0c;实现灵活的功能扩展 前言装饰者模式简介装饰者模式的工作原理实际应用java代码实现结语 前言 在软件开发中&#xff0c;我们经常面临着需求的变化和新…

rsync全面讲解

rsync 是一个常用的 Linux 应用程序&#xff0c;用于文件同步。 它可以在本地计算机与远程计算机之间&#xff0c;或者两个本地目录之间同步文件&#xff08;但不支持两台远程计算机之间的同步&#xff09;。它也可以当作文件复制工具&#xff0c;替代cp和mv命令。 它名称里面…

基础面试题整理4

1.mybatis的#{}和${}区别 #{}是预编译处理&#xff0c;${}是字符串替换#{}可以防止SQL注入&#xff0c;提高安全性 2.mybatis隔离级别 读未提交 READ UNCOMMITED&#xff1a;读到了其他事务中未提交的数据&#xff0c;造成"脏读","不可重复读","幻读&…

Python进程池multiprocessing.Pool

环境&#xff1a; 鲲鹏920:192核心 内存&#xff1a;756G python&#xff1a;3.9 python单进程的耗时 在做单纯的cpu计算的场景&#xff0c;使用单进程核多进程的耗时做如下测试&#xff1a; 单进程情况下cpu的占用了如下&#xff0c;占用一半的核心数&#xff1a; 每一步…

git 提炼笔记

1、设置用户名和邮箱&#xff08;邮箱可以不是真的&#xff09; git config --global user.name test101 // 设置用户名为 test101git config --global user.email test101test101.cn // 设置邮箱为test101test101.cn2、查看用户名和邮箱 git config --global user.name git…

【SpringBoot框架篇】35.kafka环境搭建和收发消息

kafka环境搭建 kafka依赖java环境,如果没有则需要安装jdk yum install java-1.8.0-openjdk* -y1.下载安装kafka kafka3.0版本后默认自带了zookeeper&#xff0c;3.0之前的版本需要单独再安装zookeeper,我使用的最新的3.6.1版本。 cd /usr/local wget https://dlcdn.apache.…

Redis主从架构、哨兵集群原理实战

1.主从架构简介 背景 单机部署简单&#xff0c;但是可靠性低&#xff0c;且不能很好利用CPU多核处理能力生产环境必须要保证高可用&#xff0c;一般不可能单机部署读写分离是可用性要求不高、性能要求较高、数据规模小的情况 目标 读写分离&#xff0c;扩展主节点的读能力&…

canvas绘制美队盾牌

查看专栏目录 canvas示例教程100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…