5分钟了解计数排序

约定不等于承诺〃 2023-08-17 17:34 110阅读 0赞

## 前言 ##

计数排序是一种非比较性质的排序算法，计数排序借助辅助空间记录每个元素出现的次数，根据次数确定每一个元素最终的位置。

## 计数排序思想介绍 ##

1根据待排序数组，获取最大值和最小值，得到所有元素的范围 \[m,n\]

2新建一个长度为n-m+1的临时数组

3遍历待排序数组，元素的值-m作为临时数组下标，该下标位置记录元素出现次数

4遍历结束，临时数组就存储了每个元素出现的次数

5根据该临时数组，最终得到排序后元素

算法说明：

待排序数据：12，4，6，7，4，6

数据范围为\[4,12\],临时数组长度为12-4+1=9

最终得到排序后序列：4，4，6，6，7，12

## 计数排序的代码实现 ##

1. public static void sortCount(int\[\] arr) \{

2. int max = 0;

3. int min = 0;

4. // 获取数组的最大值和最小值

5. for(int i = 0; i < arr.length; i++)\{

6. max = Math.max(max, arr\[i\]);

7. min = Math.min(min, arr\[i\]);

8. \}

9. int len = arr.length;

10. // 创建临时数组

11. int\[\] temp = new int\[max - min + 1\];

12. // 计数

13. for(int i = 0; i < len; i++) \{

14. temp\[arr\[i\] - min\] += 1;

15. \}

16. // 将临时数组中数据依次放回原数组

17. for(int i = 0, index = 0; i < temp.length; i++) \{

18. int item = temp\[i\];

19. while(item-- != 0) \{

20. arr\[index++\] = i + min;

21. \}

22. \}

23. \}

## 总结 ##

计数排序需要占用额外的存储空间，它比较适用于数据比较集中的情况。

转载于:https://www.cnblogs.com/qfchen/p/11284157.html

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关 5分钟了解折半插入排序

前言折半插入排序（Binary Insertion Sort）是对直接插入排序算法的一种改进。插入排序思想介绍折半插入排序与直接插入排序算法原理相同。只是，在向

Bertha 。/ 2024年03月17日 13:03/ 0 赞/ 128 阅读

相关 5分钟了解基数排序

5分钟了解基数排序前言基数排序无需进行比较和交换，而是利用分配和收集两种基本操作实现排序。基数排序分为两种：第一种是LSD ，从最低位开始排序；第二种是 MSD，从最

ゝ一世哀愁。/ 2023年08月17日 17:34/ 0 赞/ 188 阅读

相关 5分钟了解计数排序

前言计数排序是一种非比较性质的排序算法，计数排序借助辅助空间记录每个元素出现的次数，根据次数确定每一个元素最终的位置。计数排序思想介绍 1根据待排序数组，获取

约定不等于承诺〃/ 2023年08月17日 17:34/ 0 赞/ 111 阅读

相关 5分钟了解TypeScript

什么是TypeScript TypeScript是Microsoft公司注册商标。 TypeScript具有类型系统，且是JavaScript的超集。它可以编译成普通

谁践踏了优雅/ 2023年02月19日 05:30/ 0 赞/ 83 阅读

相关 5分钟让你了解UniApp

uni-app 是一个使用 Vue.js 开发所有前端应用的框架，开发者编写一套代码，可发布到iOS、Android、H5、以及各种小程序（微信/支付宝/百度/头条/QQ/钉钉

约定不等于承诺〃/ 2023年01月20日 03:00/ 0 赞/ 107 阅读

相关【排序】计数排序

为什么记录这个在做 [leetcode 561 题][leetcode 561]的时候，第三种解法，看了很久才明白，后来理解实际上是做了一次计数排序。这个题，直接看

缺乏、安全感/ 2022年11月20日 02:00/ 0 赞/ 297 阅读

相关 5分钟了解swagger

转自：[https://blog.csdn.net/i6448038/article/details/77622977][https_blog.csdn.net_i644803

朴灿烈づ我的快乐病毒、/ 2022年05月14日 15:04/ 0 赞/ 271 阅读

相关好程序员Java干货分享5分钟了解折半插入排序

好程序员Java干货分享5分钟了解折半插入排序，前言：折半插入排序（Binary Insertion Sort）是对直接插入排序算法的一种改进。插入排序思想介绍折半插

梦里梦外;/ 2021年11月22日 21:50/ 0 赞/ 321 阅读

相关好程序员Java教程教你5分钟了解快速排序

好程序员Java教程教你5分钟了解快速排序，前言：快速排序是面试中经常会问到的一种排序算法，对比其他一些排序算法，快速排序的平均时间相对较少。快速排序思想介绍快

傷城~/ 2021年11月22日 21:42/ 0 赞/ 291 阅读

相关计数排序

计数排序：假设n个输入元素中的每一个都是在0~区间内的一个整数，其中k为某个整数。当k=O(n)是，排序时间为O（n）. 基本思想：对每个输入元素x,确定小于x元素的

淡淡的烟草味﹌/ 2021年09月23日 03:22/ 0 赞/ 515 阅读