当前位置: 首页 > news >正文

计数排序(Count Sort)算法详解

1. 算法简介

计数排序(Count Sort)是一种非比较排序算法,其核心思想是统计数组中每个元素出现的次数,然后根据统计结果将元素按照顺序放回原数组中。计数排序的时间复杂度为O(n+k),其中n是数组的长度,k是数组中元素的取值范围。

2. 算法实现

下面是计数排序算法的Java实现:

public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}int[] bucket = new int[max + 1];for (int i = 0; i < arr.length; i++) {bucket[arr[i]]++;}int i = 0;for (int j = 0; j < bucket.length; j++) {while (bucket[j]-- > 0) {arr[i++] = j;}}
}

3. 算法原理解析

计数排序的实现步骤如下:

  1. 找到数组中的最大值max。
  2. 创建一个大小为max+1的辅助数组bucket,并将其所有元素初始化为0。
  3. 遍历原始数组arr,将每个元素的值作为bucket数组的下标,并将对应位置的元素值加1,表示该元素出现的次数。
  4. 遍历bucket数组,根据每个元素出现的次数,依次将元素放回原始数组arr中。
  5. 完成排序后,原始数组arr中的元素就按照升序排列。

4. 算法性能分析

  • 时间复杂度:计数排序的时间复杂度为O(n+k),其中n是数组的长度,k是数组中元素的取值范围。在实际应用中,当k的大小不超过n的情况下,计数排序的时间复杂度可以近似看作O(n)。
  • 空间复杂度:计数排序的空间复杂度为O(k),其中k是数组中元素的取值范围。需要额外的辅助数组bucket来统计元素出现的次数。

5. 算法应用场景

计数排序适用于以下场景:

  • 数组中的元素都是非负整数,并且取值范围相对较小。
  • 对稳定性要求较高的排序场景。

6. 算法测试与验证

为了验证计数排序算法的正确性,我们编写了以下辅助函数进行测试:

  • comparator:使用Java内置的排序函数对数组进行排序,作为验证计数排序的参照结果。
  • generateRandomArray:生成指定长度和取值范围的随机数组。
  • copyArray:复制数组,用于生成计数排序的输入数组的副本。
  • isEqual:判断两个数组是否相等。
  • printArray:打印数组。
    // 省略部分代码…
 public static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 150;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);countSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "排序正确!" : "排序错误!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);countSort(arr);printArray(arr);
}

7. 总结

计数排序是一种非比较排序算法,适用于元素取值范围较小且对稳定性要求较高的排序场景。本文通过对计数排序算法的原理、实现步骤和性能分析进行了详细讲解,并通过测试代码验证了算法的正确性。希望本文能够帮助读者更好地理解和运用计数排序算法。

完整代码

package class08;import java.util.Arrays;public class Code02_CountSort {public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}int[] bucket = new int[max + 1];for (int i = 0; i < arr.length; i++) {bucket[arr[i]]++;}int i = 0;for (int j = 0; j < bucket.length; j++) {while (bucket[j]-- > 0) {arr[i++] = j;}}}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 150;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);countSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);countSort(arr);printArray(arr);}
}

相关文章:

计数排序(Count Sort)算法详解

1. 算法简介 计数排序&#xff08;Count Sort&#xff09;是一种非比较排序算法&#xff0c;其核心思想是统计数组中每个元素出现的次数&#xff0c;然后根据统计结果将元素按照顺序放回原数组中。计数排序的时间复杂度为O(nk)&#xff0c;其中n是数组的长度&#xff0c;k是数…...

Linux驱动开发(Day3)

驱动点灯&#xff1a;...

使用Vscode调试shell脚本

在vcode中安装bash dug插件 在vcode中添加launch.json配置&#xff0c;默认就好 参考&#xff1a;http://www.rply.cn/news/73966.html 推荐插件&#xff1a; shellman(支持shell,智能提示) shellcheck(shell语法检查) shell-format(shell格式化)...

OpenAI Function calling

开篇 原文出处 最近 OpenAI 在 6 月 13 号发布了新 feature&#xff0c;主要针对模型进行了优化&#xff0c;提供了 function calling 的功能&#xff0c;该 feature 对于很多集成 OpenAI 的应用来说绝对是一个“神器”。 Prompt 的演进 如果初看 OpenAI 官网对function ca…...

【C语言】字符分类函数、字符转换函数、内存函数

前言 之前我们用两篇文章介绍了strlen、strcpy、stract、strcmp、strncpy、strncat、strncmp、strstr、strtok、streeror这些函数 第一篇文章strlen、strcpy、stract 第二篇文章strcmp、strncpy、strncat、strncmp 第三篇文章strstr、strtok、streeror 今天我们就来学习字…...

Deep Learning With Pytorch - 最基本的感知机、贯序模型/分类、拟合

文章目录 如何利用pytorch创建一个简单的网络模型&#xff1f;Step1. 感知机&#xff0c;多层感知机&#xff08;MLP&#xff09;的基本结构Step2. 超平面 ω T ⋅ x b 0 \omega^{T}xb0 ωT⋅xb0 or ω T ⋅ x b \omega^{T}xb ωT⋅xb感知机函数 Step3. 利用感知机进行决策…...

测试工具coverage的高阶使用

在文章Python之单元测试使用的一点心得中&#xff0c;笔者介绍了自己在使用Python测试工具coverge的一点心得&#xff0c;包括&#xff1a; 使用coverage模块计算代码测试覆盖率使用coverage api计算代码测试覆盖率coverage配置文件的使用coverage badge的生成 本文在此基础上…...

安卓监听端口接收消息

文章目录 其他文章监听端口接收消息 建立新线程完整代码 其他文章 下面是我的另一篇文章&#xff0c;是在电脑上发送数据&#xff0c;配合本篇文章&#xff0c;可以实现电脑与手机的局域网通讯。直接复制粘贴就能行&#xff0c;非常滴好用。 点击连接 另外&#xff0c;如果你不…...

「Node」下载安装配置node.js

以下是Node.js的下载、安装和配置的全面教程&#xff1a; 下载 Node.js 打开 Node.js 官方网站&#xff1a;Previous Releases在主页上&#xff0c;您会看到两个版本可供选择&#xff1a;LTS&#xff08;长期支持版本&#xff09;和最新版&#xff08;Current&#xff09;。如…...

NOIP2014普及组,提高组 比例简化 飞扬的小鸟 答案

比例简化 说明 在社交媒体上&#xff0c;经常会看到针对某一个观点同意与否的民意调查以及结果。例如&#xff0c;对某一观点表示支持的有1498 人&#xff0c;反对的有 902人&#xff0c;那么赞同与反对的比例可以简单的记为1498:902。 不过&#xff0c;如果把调查结果就以这种…...

【Java】使用Apache POI识别PPT中的图片和文字,以及对应的大小、坐标、颜色、字体等

本文介绍如何使用Apache POI识别PPT中的图片和文字&#xff0c;获取图片的数据、大小、尺寸、坐标&#xff0c;以及获取文字的字体、大小、颜色、坐标。 官方文档&#xff1a;https://poi.apache.org/components/slideshow/xslf-cookbook.html 官方文档和网上的资料介绍的很少…...

根据源码,模拟实现 RabbitMQ - 实现消息持久化,统一硬盘操作(3)

目录 一、实现消息持久化 1.1、消息的存储设定 1.1.1、存储方式 1.1.2、存储格式约定 1.1.3、queue_data.txt 文件内容 1.1.4、queue_stat.txt 文件内容 1.2、实现 MessageFileManager 类 1.2.1、设计目录结构和文件格式 1.2.2、实现消息的写入 1.2.3、实现消息的删除…...

找到所有数组中消失的数(C语言详解)

题目&#xff1a;找到所有数组中消失的数 题目详情&#xff1a; 给你一个含 n 个整数的数组 nums &#xff0c;其中 nums[i] 在区间 [1,n] 内。请你找出所以在 [1,n] 范围内但没有出现在 nums 中的数字&#xff0c;并以数组的形式返回结果。 示例1&#xff1a; 输入&#xf…...

计算机毕设项目之基于django+mysql的疫情实时监控大屏系统(前后全分离)

系统阐述的是一款新冠肺炎疫情实时监控系统的设计与实现&#xff0c;对于Python、B/S结构、MySql进行了较为深入的学习与应用。主要针对系统的设计&#xff0c;描述&#xff0c;实现和分析与测试方面来表明开发的过程。开发中使用了 django框架和MySql数据库技术搭建系统的整体…...

Unity UI内存泄漏优化

项目一运行&#xff0c;占用的内存越来越多&#xff0c;不会释放&#xff0c;导致GC越来越频繁&#xff0c;越来越慢&#xff0c;这些都是为什么呢&#xff0c;今天从UI方面谈起。 首先让我们来聊聊什么是内存泄漏呢&#xff1f; 一般来讲内存泄漏就是指我们的应用向内存申请…...

学习笔记:Opencv实现图像特征提取算法SIFT

2023.8.19 为了在暑假内实现深度学习的进阶学习&#xff0c;特意学习一下传统算法&#xff0c;分享学习心得&#xff0c;记录学习日常 SIFT的百科&#xff1a; SIFT Scale Invariant Feature Transform, 尺度不变特征转换 全网最详细SIFT算法原理实现_ssift算法_Tc.小浩的博客…...

【golang】接口类型(interface)使用和原理

接口类型的类型字面量与结构体类型的看起来有些相似&#xff0c;它们都用花括号包裹一些核心信息。只不过&#xff0c;结构体类型包裹的是它的字段声明&#xff0c;而接口类型包裹的是它的方法定义。 接口类型声明中的这些方法所代表的就是该接口的方法集合。一个接口的方法集…...

【Linux操作系统】Linux系统编程中的共享存储映射(mmap)

在Linux系统编程中&#xff0c;进程之间的通信是一项重要的任务。共享存储映射&#xff08;mmap&#xff09;是一种高效的进程通信方式&#xff0c;它允许多个进程共享同一个内存区域&#xff0c;从而实现数据的共享和通信。本文将介绍共享存储映射的概念、原理、使用方法和注意…...

2235.两整数相加:19种语言解法(力扣全解法)

【LetMeFly】2235.两整数相加&#xff1a;19种语言解法&#xff08;力扣全解法&#xff09; 力扣题目链接&#xff1a;https://leetcode.cn/problems/add-two-integers/ 给你两个整数 num1 和 num2&#xff0c;返回这两个整数的和。 示例 1&#xff1a; 输入&#xff1a;num…...

中国剩余定理及扩展

目录 中国剩余定理解释 中国剩余定理扩展——求解模数不互质情况下的线性方程组&#xff1a; 代码实现&#xff1a; 互质&#xff1a; 非互质&#xff1a; 中国剩余定理解释 在《孙子算经》中有这样一个问题&#xff1a;“今有物不知其数&#xff0c;三三数之剩二&#x…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...