当前位置:网站首页>计数排序基础思路
计数排序基础思路
2022-07-06 22:04:00 【就要 宅在家】
所谓计数排序,也可以称为散列表 。也是一种简单的哈希桶。
今天,小编带大家来了解计数排序的基本思路。
一。基本思路
以升序为例,计数排序通俗来讲,分为三个步骤。
首先制作包含所有要排序的数的桶(相同的数制作一个桶即可)。
以2,3,6,1,4,1,2,3,7,6,8,9,5,4,3举例,就是制作9个桶,分别代表1,2,3,4,5,6,7,8,9。
第二步, 把所有的数依次放入桶中,桶中的数字代表该数有多少个。
第三步,从小到大依次把桶中的数全部拿出来。
排序完成。
小编希望大家自主实现一下代码,难度不大,相信自己!
ps:桶可以用数组下标代替。
二。代码实现
void CountSort(int* a, int n)
{
if (n <= 0) return;
assert(a);
int min = a[0], max = a[0];
for (int i = 0; i < n; i++)//找出排序范围,减少空间浪费
{
if (min > a[i]) min = a[i];
if (max < a[i]) max = a[i];
}
int* tmp = (int*)new int[max - min + 1], range = max - min + 1;
memset(tmp, 0, sizeof(int) * range);
for (int i = 0; i < n; i++)//入桶
{
tmp[a[i] - min]++;
}
int sub = 0;
for (int i = 0; i < range; i++)//出桶
{
while (tmp[i]--)
{
a[sub++] = i + min;
}
}
}
三。问题
时间复杂度:O(n)
空间复杂度:O(n)
计数排序的作用范围狭小,浮点数、结构体之类都不适用,且范围越大空间复杂度和空间浪费就越明显。
三连支持一下吧 如有错误,敬请斧正
边栏推荐
- 接口自动化测试实践指导(中):接口测试场景有哪些
- 英特尔与信步科技共同打造机器视觉开发套件,协力推动工业智能化转型
- Unity3d can change colors and display samples in a building GL material
- 见到小叶栀子
- [record of question brushing] 2 Add two numbers
- UltraEdit-32 warm prompt: right association, cancel bak file [easy to understand]
- leetcode 53. Maximum Subarray 最大子数组和(中等)
- [ArcGIS tutorial] thematic map production - population density distribution map - population density analysis
- How to open win11 remote desktop connection? Five methods of win11 Remote Desktop Connection
- leetcode 53. Maximum Subarray 最大子数组和(中等)
猜你喜欢
Common methods of list and map
[ArcGIS tutorial] thematic map production - population density distribution map - population density analysis
Food Chem | in depth learning accurately predicts food categories and nutritional components based on ingredient statements
这项15年前的「超前」技术设计,让CPU在AI推理中大放光彩
Mathematical analysis_ Notes_ Chapter 10: integral with parameters
The most complete deployment of mongodb in history
What if win11 pictures cannot be opened? Repair method of win11 unable to open pictures
How do test / development programmers get promoted? From nothing, from thin to thick
Ssm+jsp realizes enterprise management system (OA management system source code + database + document +ppt)
EasyCVR平台接入RTMP协议,接口调用提示获取录像错误该如何解决?
随机推荐
高薪程序员&面试题精讲系列120之Redis集群原理你熟悉吗?如何保证Redis的高可用(上)?
英特尔与信步科技共同打造机器视觉开发套件,协力推动工业智能化转型
Case reward: Intel brings many partners to promote the innovation and development of multi domain AI industry
掌握软件安全测试方法秘笈,安全测试报告信手捏来
5年自动化测试,终于进字节跳动了,年薪30w其实也并非触不可及
Master the secrets of software security testing methods, and pinch the security test report with your hands
[multi threading exercise] write a multi threading example of the producer consumer model.
每人每年最高500万经费!选人不选项目,专注基础科研,科学家主导腾讯出资的「新基石」启动申报
广告归因:买量如何做价值衡量?
Both primary and secondary equipment numbers are 0
[team learning] [phase 34] Baidu PaddlePaddle AI talent Creation Camp
过气光刻机也不能卖给中国!美国无理施压荷兰ASML,国产芯片再遭打压
The most complete security certification of mongodb in history
Intel and Xinbu technology jointly build a machine vision development kit to jointly promote the transformation of industrial intelligence
The worse the AI performance, the higher the bonus? Doctor of New York University offered a reward for the task of making the big model perform poorly
Gpt-3 is a peer review online when it has been submitted for its own research
Opencv third party Library
Digital chemical plant management system based on Virtual Simulation Technology
Win11远程桌面连接怎么打开?Win11远程桌面连接的五种方法
Comment les tests de logiciels sont - ils effectués sur le site Web? Testez la stratégie!