【数据结构】计数排序的原理及实现

news/2024/12/12 19:32:49/

在这里插入图片描述

👦个人主页:Weraphael
✍🏻作者简介:目前正在准备26考研
✈️专栏:数据结构
🐋 希望大家多多支持,咱一起进步!😁
如果文章有啥瑕疵,希望大佬指点一二
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍


目录

  • 一、计数排序的介绍
  • 二、算法流程
  • 三、代码实现
  • 四、时空复杂度分析

一、计数排序的介绍

计数排序和基数排序一样,是一种非比较排序算法,它的基本思想是:

  1. 统计输入数据中每个元素出现的次数。
  2. 然后根据这些计数信息将元素按顺序放置在正确的位置。最后数组就有序了。

算法思想非常简单,如果还有不理解的话可以看看下面的算法流程。当然也建议看看,因为编写代码的基础都是来源于它~

二、算法流程

比方说序列a = [4, 2, 2, 5, 3, 3, 1],要求通过计数排序将原序列排位升序

如果按照以上序列的话,计数数组至少要开原数组中的最大值 + 1。因为我们要保证原序列的每个元素在计数数组中都能映射到相应的位置。并且,计数数组的每一个位置都要初始化为0

请添加图片描述

接下来就要统计原数组中每个元素出现的个数并映射到计数数组中

请添加图片描述

最后,根据计数数组的信息,将元素按照顺序从左往右填充回原数组

请添加图片描述

看到这里,我相信你已经完全理解了计数排序。但接下来需要处理一些细节问题。

比方说,当序列为a = [1000, 1001, 3000, 4000]。难道你的计数数组还需要开原数组中的最大值 + 1,即4001个吗?这不妥妥的浪费空间!所以,我们其实仅需开[1000, 4001)即可。因此,计数数组的空间大小是由原数组中的最大值和最小值来决定的。(注:计数数组大小 = 最大值 - 最小值 + 1

  • 映射数组元素到计数数组的位置不再是countArr[a[i]]++,而是countArr[a[i] − min_val]++。(减去偏移量即可将元素值转化为计数数组中的索引)
  • 同理,因为计数数组的下标已经不对应原序列的元素值了。因此,当我们根据这些计数信息将元素按顺序放置在正确的位置时,即遍历计数数组时,是需要通过当前下标 + min_val即可以得到原数组的值。

三、代码实现

// 计数排序
void count_Sort(int a[], int n)
{// 数组只有一个数或者没有,就没必要排序了if (n < 2) return; // 1. 确定计数数组的大小(获取原序列的最大值和最小值)int max_val = a[0], min_val = a[0];for (int i = 1; i < n; i++){if (a[i] > max_val){max_val = a[i];}if (min_val > a[i]){min_val = a[i];}}// 2. 为计数数组开辟空间// 范围是 max_val - min_val + 1int range = max_val - min_val + 1;// calloc默认会将空间全部初始化为0int* countArr = (int*)calloc(range, sizeof(int)); // 3. 统计原数组每个元素出现的个数, 并映射到计数数组中for (int i = 0; i < n; i++){countArr[a[i] - min_val]++;}// 4. 遍历计数数组,将结果写会原数组int index = 0;for (int i = 0; i < range; i++){while (countArr[i]--){a[index] = i + min_val;index++;}}// 排完序后别忘了释放内存空间~free(countArr);
}

【输出结果】

请添加图片描述

四、时空复杂度分析

  • 确定计数数组的大小时,遍历了一遍原序列。因此时间复杂度是O(n)

  • 统计原数组每个元素出现的个数, 并映射到计数数组中,时间复杂度还是O(n)

  • 遍历计数数组,时间复杂度是O(max_val - min_val + 1),记作为O(k)

加起来的话就是T(n) = O(n) + O(n) + O(k)。因此,计数排序的时间复杂度就是O(n + k)。注意O(k)不能舍弃,如果原序列存在非常大的元素,那么计数排序的空间复杂度O(k)可能会变得非常高,近似O(n^2),这时计数排序就不适用了。同时也会存在浪费空间的现象。因此,计数排序适用于数据范围较小,数据是整数或可以映射到整数的离散值(如字符、日期等)。主要还是数据范围较小!!!

而空间复杂度就不用说了,就是O(K)


http://www.ppmy.cn/news/1554578.html

相关文章

Android APP自学笔记

摘抄于大学期间记录在QQ空间的一篇自学笔记&#xff0c;当前清理空间&#xff0c;本来想直接删除掉的&#xff0c;但是感觉有些舍不得&#xff0c;因此先搬移过来。 Android导入已有外部数据库 2015.06.26在QQ空间记录&#xff1a;在Android中不能直接打开res aw目录中的数据…

【MIT-OS6.S081作业1.3】Lab1-utilities primes

本文记录MIT-OS6.S081 Lab1 utilities 的primes函数的实现过程 文章目录 1. 作业要求primes (moderate)/(hard) 2. 实现过程2.1 代码实现 1. 作业要求 primes (moderate)/(hard) Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, in…

蓝桥杯我来了

最近蓝桥杯报名快要截止了&#xff0c;我们学校开始收费了&#xff0c;我们学校没有校赛&#xff0c;一旦报名缴费就是省赛&#xff0c;虽然一早就在官网上报名了&#xff0c;但是一直在纠结&#xff0c;和家人沟通&#xff0c;和朋友交流&#xff0c;其实只是想寻求外界的支持…

分布式 CAP理论 总结

前言 相关系列 《分布式 & 目录》《分布式 & CAP理论 & 总结》《分布式 & CAP理论 & 问题》 分布式 分布式的核心是将大型业务拆解成多个子业务以使之在不同的机器上执行。分布式是用于解决单个物理机容量&性能瓶颈问题而采用的优化手段&#xf…

革新医疗器械生产:MR30分布式IO模块引领智能制造新纪元

在当今快速发展的医疗科技领域&#xff0c;高效、精准与安全性是衡量医疗器械生产线的金标准。随着工业4.0时代的到来&#xff0c;分布式IO&#xff08;Input/Output&#xff0c;输入/输出&#xff09;模块以其灵活、高效、可靠的特点&#xff0c;正逐步成为医疗器械生产线智能…

vue element 切换 select 下拉框的 单选多选报错

今天根据项目需求&#xff0c;需要对下拉框进行&#xff0c;单双选判断&#xff0c;当多选切换成多选&#xff0c;没有问题但是单选切换成多选报错如下 页面是要求 选择in或者notin时候 多选 经过好长时间摸索&#xff0c;解决了&#xff0c;最后使用select的失去焦点事件解决…

深入理解Java虚拟机(JVM)

深入理解Java虚拟机&#xff08;JVM&#xff09;&#xff1a;架构、内存模型与性能调优 Java虚拟机&#xff08;JVM&#xff09;是Java程序的运行时环境&#xff0c;作为Java技术的核心之一&#xff0c;它提供了一个抽象的计算平台&#xff0c;使Java程序能够在不同的硬件和操作…

华为HarmonyOS NEXT 原生应用开发: 数据持久化存储(用户首选项)的使用 token令牌存储鉴权!

Preferences 数据持久化存储 用户首选项&#xff08;Preferences&#xff09; 1. 封装 仓库工具类 ● 这里可以选择将 数据字段 key 抽取为一个静态方法&#xff0c;这里选择让用户传参&#xff0c;看起来较容易理解&#xff01; /*** 首选项 preferences - 实现数据持久化…