【非比较排序】计算排序算法

目录

CountSort计数排序

整体思想

图解分析

代码实现

时间复杂度&优缺分析


CountSort计数排序

计数排序是一种非比较排序,不需要像前面的排序一样去比较。

计数排序的特性总结:
1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
2. 时间复杂度:O(MAX(N,范围))
3. 空间复杂度:O(范围)

4. 稳定性:稳定 

整体思想

  • 思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。
  • 1. 统计相同元素出现次数
  • 2. 根据统计的结果将序列回收到原来的序列中 

Count数组

  • Count数组中的元素需要全部初始化为0(calloc就可以满足这个要求)
  • Count元素是 计算a数组元素个数出现的次数
  • Count数组的下标是a数组元素的范围
  • 绝对隐射:范围0~max(a中最大的元素)
  • 相对隐射:范围0~max-min <<<<<<<<< min~max
  • range = max-min+1(映射0~max-min,个数max-min+1)

整个流程

  • 遍历一遍:找到最大值 / 最小值
  • 计算出Count数组下标范围并且开辟动态空间
  • rangge=max-min+1
  • 计数Count[a[i]-min]++ (i++)
  • 相对隐射回去

注意tips

  • i和j能不能公用❓
  • a数组的元素可以是负数吗?
  • 除了整型其他类型可以吗?
  • 后置--&前置--

  • calloc>>>>>>calloc - C++ Reference (cplusplus.com)
  • Count的下标表示a的元素的范围
  • Count的元素表示a的元素出现的个数(计数)

图解分析

代码实现

void CountSort(int* a, int n)
{
	//找最大值/最小值/创建的tmp的范围在这个之间
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}

	int range = max - min + 1;//注意
	int* count = (int*)calloc(range, sizeof(int));
	//计数
	for (int j = 0; j < n; j++)
	{
		count[a[j]-min]++;
	}

	//相对隐射回去
	int i = 0;
	for (int k = 0; k < range; k++)
	{
		while (count[k]--)
		{
			a[i++] = k + min;
		}
	}
}

时间复杂度&优缺分析

时间复杂度:O(N)

  • 时间复杂度:O(a(N)+coun(N))(count的N是a的数据范围)
  • 计数排序不需要比较元素大小
  • 优势:效率极高
  • 局限性:不适合范围很大,计数排序只适用于整型,不同数据类型的,实践意义不高。(现实实践,更多的是结构体排序,不能适用计数排序)

🙂感谢大家的阅读,若有错误和不足,欢迎指正。下篇总结各个排序。

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

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

相关文章

【element+vue】点击加号增加一行,点击减号删除一行

代码实现&#xff1a; 页面部分&#xff1a; vueelement 备注&#xff1a;v-if “i>0” &#xff08;保证第一行不出现减号&#xff09; <div v-for"(item,i) in studentList"><el-form-item label"学生:" prop"name"><el-i…

基于Java SSM框架实现家庭食谱管理系统项目【项目源码+论文说明】计算机毕业设计

基于java的SSM框架实现家庭食谱管理系统演示 摘要 本论文主要论述了如何使用JAVA语言开发一个家庭食谱管理系统 &#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将论…

智慧公厕:打造智慧城市环境卫生新标杆

随着科技的不断发展和城市化进程的加速推进&#xff0c;智慧城市建设已经成为各地政府和企业关注的焦点。而作为智慧城市环境卫生管理的基础设施&#xff0c;智慧公厕的建设和发展也备受重视&#xff0c;被誉为智慧城市的新标杆。本文以智慧公厕源头厂家广州中期科技有限公司&a…

Ubuntu22.04环境下载安装中文搜狗输入法

0、查看CPU系统架构 确定架构后&#xff0c;下载对应的安装包&#xff0c;否则无法正常安装应用程序 1、进入搜狗拼音输入法官网&#xff0c;下载搜狗输入法 搜狗输入法-首页搜狗拼音输入法官网下载&#xff0c;荣获多个国内软件大奖的搜狗拼音输入法是一款打字更准、词库更大…

2024年【安全员-A证】考试及安全员-A证模拟考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 安全员-A证考试根据新安全员-A证考试大纲要求&#xff0c;安全生产模拟考试一点通将安全员-A证模拟考试试题进行汇编&#xff0c;组成一套安全员-A证全真模拟考试试题&#xff0c;学员可通过安全员-A证模拟考试全真模…

【Python数据分析系列】多个dataframe写入同一个excel文件(案例源码)

一、引言 将多个DataFrame写入同一个excel文件中&#xff0c;每个DataFrame作为一个sheet&#xff0c;可以使用pandas库中的ExcelWriter类。这个类可以在一个Excel文件中创建多个sheet&#xff0c;并将不同的数据写入这些sheet中。本文演示如何将多个DataFrame写入同一个CSV文件…

抖音视频评论抓取软件|视频批量下载

抖音视频评论采集软件是一款基于C#开发的高效、便捷的工具&#xff0c;旨在为用户提供全面的数据采集和分析服务。该软件不仅支持通过关键词进行搜索抓取&#xff0c;还能够通过分享链接进行单个视频的抓取和下载&#xff0c;让用户轻松获取抖音视频评论数据。 &#x1f50d; …

uniapp 安卓GPS定位原生插件

插件介绍 安卓GPS定位插件&#xff0c;支持获取定位权限&#xff0c;获取上一次的定位信息&#xff0c;持续定位监听&#xff0c;取消定位监听&#xff0c;可返回详细街道信息 插件地址 安卓GPS定位插件&#xff0c;支持持续定位监听&#xff0c;支持返回详细街道信息 - DCl…

springboot003图书个性化推荐系统的设计与实现(源码+调试+LW)

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。今天给大家介绍一篇基于SpringBoot的图书个…

web安全学习笔记【17】——信息打点(7)

信息打点-APP资产&知识产权&应用监控&静态提取&动态抓包&动态调试 #知识点&#xff1a; 1、业务资产-应用类型分类 2、Web单域名获取-接口查询 3、Web子域名获取-解析枚举 4、Web架构资产-平台指纹识别 ------------------------------------ 1、开源-CMS指…

切比雪夫(最小区域法)球拟合算法

欢迎关注更多精彩 关注我&#xff0c;学习常用算法与数据结构&#xff0c;一题多解&#xff0c;降维打击。 本期话题&#xff1a;切比雪夫&#xff08;最小区域法&#xff09;球拟合算法 相关背景和理论 点击前往 主要介绍了应用背景和如何转化成线性规划问题 球拟合输入和输…

【Python笔记-设计模式】命令模式

一、说明 命令模式是一种行为设计模式&#xff0c;旨在对命令的封装&#xff0c;根据不同的请求将方法参数化、延迟请求执行或将其放入队列中&#xff0c;且能实现可撤销操作。 (一) 解决问题 将请求发送者和接受者解耦&#xff0c;请求发送者只需知道如何发送请求&#xff…

【力扣hot100】刷题笔记Day14

前言 又是新的一周&#xff0c;快乐的周一&#xff0c;快乐地刷题&#xff0c;今天把链表搞完再干活&#xff01; 114. 二叉树展开为链表 - 力扣&#xff08;LeetCode&#xff09; 前序遍历 class Solution:def flatten(self, root: Optional[TreeNode]) -> None:if not r…

Ubontu更换软件包源库来提高下载速度

对于 apt-get update 运行缓慢的问题&#xff0c;您可以尝试更换软件包源库来提高下载速度。在 Debian 系统中&#xff0c;可以通过编辑 /etc/apt/sources.list 文件来更改软件包源 1、打开 /etc/apt/sources.list 文件&#xff1a;使用文本编辑器&#xff08;例如 vi、nano 或…

Linux使用Docker部署Traefik容器并实现远程访问管理界面

文章目录 一、Zotero安装教程二、群晖NAS WebDAV设置三、Zotero设置四、使用公网地址同步Zotero文献库五、使用永久固定公网地址同步Zotero文献库 Zotero 是一款全能型 文献管理器,可以 存储、管理和引用文献&#xff0c;不但免费&#xff0c;功能还很强大实用。 ​ Zotero 支…

React Hooks概述及常用的React Hooks介绍

Hook可以让你在不编写class的情况下使用state以及其他React特性 useState ● useState就是一个Hook ● 通过在函数组件里调用它来给组件添加一些内部state,React会在重复渲染时保留这个state 纯函数组件没有状态&#xff0c;useState()用于设置和使用组件的状态属性。语法如下…

StarRocks之监控管理(内含DashBoard模板)

先看下最终效果图 架构 Prometheus 是一个拥有多维度数据模型的、灵活的查询语句的时序数据库。它可以通过 Pull 或 Push 采集被监控系统的监控项,存入自身的时序数据库中。并且通过丰富的多维数据查询语言,满足用户的不同需求。 Grafana 是一个开源的 Metric 分析及可视化系…

springboot-基础-添加model和controller的简单例子+常用注解含义

备份笔记。所有代码都是2019年测试通过的&#xff0c;如有问题请自行搜索解决&#xff01; 上一篇&#xff1a;springboot-基础-eclipse配置helloword示例 目录 添加model和controller的例子注解开发使用RestController 大坑 添加model和controller的例子 文件结构&#xff1…

Vue.js+SpringBoot开发快递管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容2.1 数据中心模块2.2 快递类型模块2.3 快递区域模块2.4 快递货架模块2.5 快递档案模块 三、界面展示3.1 登录注册3.2 快递类型3.3 快递区域3.4 快递货架3.5 快递档案3.6 系统基础模块 四、免责说明 一、摘要 1.1 项目介绍 …

(AtCoder Beginner Contest 340) -- F - S = 1 -- 题解

目录 F - S 1&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 代码实现&#xff1a; F - S 1&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 这道题需要解决的就是三角形面积怎么用 A、B、X、Y&#xff0c;表示。 exgcd求解大致思路&#xff1a;可看C…