排序算法---计数排序

原创不易,转载请注明出处。欢迎点赞收藏~

计数排序(Counting Sort)是一种线性时间复杂度的排序算法,其核心思想是通过统计待排序元素的个数来确定元素的相对位置,从而实现排序。

具体的计数排序算法步骤如下:
1. 找出待排序数组中的最大值,并创建一个统计数组count[],其长度为最大值加1。
2. 遍历待排序数组,统计每个元素出现的次数,将统计结果存储在count[]数组中。count[i]表示元素i出现的次数。
3. 对count[]数组进行累加,得到每个元素在排序后的数组中的最后一个位置。即count[i]表示小于等于元素i的元素个数。
4. 创建一个临时数组temp[],其长度与待排序数组相同。
5. 逆序遍历待排序数组,根据count[]数组中的记录,将每个元素放入temp[]数组中的正确位置。
6. 将temp[]数组的元素复制回待排序数组,完成排序。

计数排序的时间复杂度为O(n+k),其中n是待排序数组的长度,k是待排序数组中的最大值。由于需要创建额外的count[]和temp[]数组,所以空间复杂度为O(n+k)。

需要注意的是,计数排序适用于元素范围较小且非负整数的排序,如果待排序数组包含负数或者小数,则需要进行适当的转换或调整。计数排序是稳定的排序算法,因为相同元素的相对顺序在排序后保持不变,但它不是基于比较的排序算法,因此在某些情况下比其他排序算法更高效。

下面是一个使用C语言实现的计数排序示例:

#include <stdio.h>void counting_sort(int arr[], int n)
{int max = arr[0];// 找出最大值for (int i = 1; i < n; i++){if (arr[i] > max){max = arr[i];}}// 创建统计数组count[],并初始化为0int count[max + 1];for (int i = 0; i <= max; i++){count[i] = 0;}// 统计每个元素的次数for (int i = 0; i < n; i++){count[arr[i]]++;}// 累加count[]数组,表示小于等于元素i的元素个数for (int i = 1; i <= max; i++){count[i] += count[i - 1];}// 创建临时数组temp[],存储排好序的元素int temp[n];// 根据count[]数组中的记录,将元素放入temp[]数组的正确位置for (int i = n - 1; i >= 0; i--){temp[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}// 将temp[]数组的元素复制回原数组arr[]for (int i = 0; i < n; i++){arr[i] = temp[i];}
}int main()
{int arr[] = {9, 3, 6, 1, 3, 2, 9, 0};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}counting_sort(arr, n);printf("\n排序后的数组: \n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}putchar('\n');return 0;
}

这段代码实现了计数排序算法。主要包括以下步骤:

1.遍历数组找出最大值,确定统计数组count[]的长度。
2.创建并初始化统计数组count[],长度为最大值加1。
3.遍历数组,统计每个元素的出现次数,存储在count[]中。
4.累加count[]数组,表示小于等于元素i的元素个数。
5.创建临时数组temp[],用于存储排好序的元素。
6.逆序遍历原数组,根据count[]数组中的记录,将元素放入temp[]数组的正确位置。
7.将temp[]数组的元素复制回原数组arr[],完成排序。

运行如上代码,你可以看到以下输出:

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

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

相关文章

基于Python实现Midjourney集成到(个人/公司)平台中

目前Midjourney没有对外开放Api&#xff0c;想体验他们的服务只能在discord中进入他们的频道进行体验或者把他们的机器人拉入自己创建的服务器中&#xff1b;而且现在免费的也用不了了&#xff0c;想使用就得订阅。本教程使用midjourney-api这个开源项目&#xff0c;搭建Midjou…

鸿蒙开发-HarmonyOS UI架构

初步布局Index 当我们新建一个工程之后&#xff0c;首先会进入Index页。我们先简单的做一个文章列表的显示 class Article {title?: stringdesc?: stringlink?: string }Entry Component struct Index {State articles: Article[] []build() {Row() {Scroll() {Column() …

Web项目利用MybatisPlus进行分页查询

之前在写博客系统前台页面的时候&#xff0c;遇到了利用mp进行分页查询的情况&#xff0c;由于涉及到的知识点相对较为重要&#xff0c;固写一篇博客以此巩固。 一、功能需求 在首页和分类页面都需要查询文章列表。 首页&#xff1a;查询所有的文章分类页面&#xff1a;查询…

云计算基础-网络虚拟化

虚拟交换机 什么是虚拟交换机 虚拟交换机是一种运行在虚拟化环境中的网络设备&#xff0c;其运行在宿主机的内存中&#xff0c;通过软件方式在宿主机内部实现了部分物理交换机的功能&#xff0c;如 VLAN 划分、流量控制、QoS 支持和安全功能等网络管理特性 虚拟交换机在云平…

Invalid DataSize: cannot convert ‘30Mb‘ to Long

Invalid DataSize: cannot convert 30Mb to Long servlet:multipart:max-file-size: 30MBmax-request-size: 30MB

Mysql5.6忘记密码,如何找回(windows)

mysql5.6安装 第一步&#xff1a;关闭正在运行的数据库服务 net stop mysql第二步&#xff1a;在my.ini文件当中的[mysqld] 任意一个位置放入 skip-grant-tables第三步&#xff1a;启动mysql服务 net start mysql第四步&#xff1a;服务启动成功后就可以登录了&#xff0c;…

数据库管理-第149期 Oracle Vector DB AI-01(20240210)

数据库管理149期 2024-02-10 数据库管理-第149期 Oracle Vector DB & AI-01&#xff08;20240210&#xff09;1 机器学习2 向量3 向量嵌入4 向量检索5 向量数据库5 专用向量数据库的问题总结 数据库管理-第149期 Oracle Vector DB & AI-01&#xff08;20240210&#xf…

Typora+PicGO+腾讯云COS做图床教程

文章目录 Typora&#xff0b;PicGO&#xff0b;腾讯云COS做图床教程一、为什么使用图床二、Typora、PicGO和腾讯云COS介绍三、下载Typora和PicGOTyporaPicGO 四、配置Typora、PicGO和腾讯云COS腾讯云COS配置PicGO配置Typora配置 Typora&#xff0b;PicGO&#xff0b;腾讯云COS做…

【教学类-19-08】20240214《ABAB式-规律黏贴18格-手工纸15*15CM-一页3种图案,A空,纵向、无边框》(中班)

背景需求 利用15*15CM手工纸制作AB色块手环&#xff08;手工纸自带色彩&#xff09;&#xff0c;一页3个图案&#xff0c;2条为一组&#xff0c;黏贴成一个手环 素材准备 代码展示 # # 作者&#xff1a;阿夏 # 时间&#xff1a;2024年2月14日 # 名称&#xff1a;正方形数字卡…

OpenTitan- 开源安全芯片横空出世

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

【PyQt6]全屏截图实现的带密码锁屏功能

文章目录 1. 简介2. Demo 1. 简介 书接上回&#xff0c;PyQt6 使用 QScreen 实现了截图&#xff0c;如果用个控件全屏显示截图&#xff0c;嘿嘿&#xff0c;那就是简单的一个锁屏界面了&#xff0c;类似于一个假死界面&#xff0c;也挺有意思。 友情提醒 输入 quit 可以退出程…

前端vue 数字 字符串 丢失精度问题

1.问题 后端返回的数据 是这样的 一个字符串类型的数据 前端要想显示这个 肯定需要使用Json.parse() 转换一下 但是 目前有一个问题 转换的确可以 showId:1206381711026823172 有一个这样的字段 转换了以后 发现 字段成了1206381711026823200 精度直接丢了 原本的数据…

SAP PP学习笔记- 豆知识01 - 怎么查询既存品目

SAP系统当中已经有哪些品目要怎么查询呢&#xff1f; 1&#xff0c;MM60 品目一览 这里可以输入Plant&#xff0c;然后可以查询该工厂的所有品目。 2&#xff0c;SE16 > MARA MARA 品目一般Data&#xff0c;存放的是品目基本信息。 如果要查询该品目属于哪个Plant&#x…

[计算机网络]---序列化和反序列化

前言 作者&#xff1a;小蜗牛向前冲 名言&#xff1a;我可以接受失败&#xff0c;但我不能接受放弃 如果觉的博主的文章还不错的话&#xff0c;还请点赞&#xff0c;收藏&#xff0c;关注&#x1f440;支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、再谈协议…

杨中科 ASP.NET DI综合案例

综合案例1 需求说明 1、目的:演示DI的能力; 2、有配置服务、日志服务&#xff0c;然后再开发一个邮件发送器服务。可以通过配置服务来从文件、环境变量、数据库等地方读取配置&#xff0c;可以通过日志服务来将程序运行过程中的日志信息写入文件、控制台、数据库等。 3、说明…

linux-firewalld防火墙端口转发

目的:通过统一地址实现对外同一地址暴露 1.系统配置文件开启 ipv4 端口转发 echo "net.ipv4.ip_forward 1" >> /etc/sysctl.confsysctl -p 2.查看防火墙配置端口转发之前的状态 firewall-cmd --statefirewall-cmd --list-all 3.开启 IP 伪装 firewall-cm…

6、内网安全-横向移动WmiSmbCrackMapExecProxyChainsImpacket

用途&#xff1a;个人学习笔记&#xff0c;有所借鉴&#xff0c;欢迎指正&#xff01; 前言&#xff1a; 在内网环境中&#xff0c;主机192.168.3.31有外网网卡能出网&#xff0c;在取得该主机权限后上线&#xff0c;搭建web应用构造后门下载地址&#xff0c;利用该主机执行相…

【漏洞复现】狮子鱼CMS文件上传漏洞(wxapp.php)

Nx01 产品简介 狮子鱼CMS&#xff08;Content Management System&#xff09;是一种网站管理系统&#xff0c;它旨在帮助用户更轻松地创建和管理网站。该系统拥有用户友好的界面和丰富的功能&#xff0c;包括页面管理、博客、新闻、产品展示等。通过简单直观的管理界面&#xf…

JavaWeb之Servlet接口

Servlet接口 什么是Servlet&#xff1f; Servlet是一种基于Java技术的Web组件&#xff0c;用于生成动态内容&#xff0c;由容器管理&#xff0c;是平台无关的Java类组成&#xff0c;并且由Java Web服务器加载执行&#xff0c;是Web容器的最基本组成单元 什么是Servlet容器&…

【后端高频面试题--设计模式上篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 往期精彩内容 【后端高频面试题–设计模式上篇】 【后端高频面试题–设计模式下篇】 【后端高频…