计数排序算法
C语言题库
共 4028字,需浏览 9分钟
· 2021-07-03
01
—
计数排序原理
假设输入n个元素,每个元素在区间0~k内的一个整数,区间k是最大值和最小值之间的区间。假如输入元素最大值是5,最小值是2,那么区间k=5 - 2 + 1 = 4。
计数排序算法思想:对于每一个输入元素x,确定小于等于元素x的个数,按照小于等于元素x的个数确定元素x在输出序列的索引。当有相同元素时,相同的元素要依次排列。
—
计数排序实现
小于元素x的个数正是元素x在输出序列中对应的索引(索引从0开始),考虑到序列可有相同的元素,同时又要保持Q(n)的时间复杂度,新建一个k大小的缓冲区,依次保存各个元素对应的索引值,如下图所示。
图中-1的索引表示无效索引,最后遍历原始序列,按照各个元素的对应的索引存放在输出序列中,相同元素依次排列,对应k区间内的保存的索引值加1。最终输出序列如下图所示。
计数排序算法实现代码如下:
void count_sort(int *input, int input_length, int *output, int output_length){
if(input == NULL || output == NULL || output_length < input_length){
return;
}
int k = 0, max, min;
int i = 0;
min = input[0];
max = input[0];
//找出最大值和最小值
for(i = 0; i < input_length; i++){
if(input[i] < min){
min = input[i];
}
if(input[i] > max){
max = input[i];
}
}
k = max - min + 1; //求出数值区间
int *temp = (int *)malloc(sizeof(int) * k);
int *index = (int *)malloc(sizeof(int) * k);
if(temp == NULL){
return;
}
memset(temp, 0, sizeof(int) * k);
memset(index, -1, sizeof(int) * k);
int count = 0;
for(i = 0; i < input_length; i++){
temp[input[i] - min]++; //统计input里每个元素的个数
}
for(i = 0; i <= k; i++){
count = temp[i];
if(i > 0){
temp[i] = temp[i] + temp[i - 1]; //统计input小于等于各个元素值的个数
}
if(count > 0){
index[i] = temp[i] - count; //求出各个元素在输出序列中对应的索引值
}
}
for(i = input_length - 1; i >= 0; i--){
output[index[input[i] - min]] = input[i]; //将原始序列中的元素存放在输出序列对应索引中
index[input[i] - min]++; //相同的数据相邻放置
temp[input[i] - min]--;
}
free(temp);
free(index);
}
写一个小程序验证计数排序算法的正确性。
#include <stdio.h>
#include "count_sort.h"
#define MAX_LENGTH 10
int main() {
int input[MAX_LENGTH] = {1, 2, -3, 6, 7, 9, 3, 5, 4, 2};
int output[MAX_LENGTH] = {0};
count_sort(input, MAX_LENGTH, output, MAX_LENGTH);
int i = 0;
printf("计数排序输出结果\n");
for(i = 0; i < MAX_LENGTH; i++){
printf("%d ", output[i]);
}
printf("\n");
return 0;
}
编译运行输出如下:
计数排序输出结果
-3 1 2 2 3 4 5 6 7 9
算法完全正确。
评论
面试官:限流的常见算法有哪些?
限流的实现算法有很多,但常见的限流算法有三种:计数器算法、漏桶算法和令牌桶算法。1.计数器算法计数器算法是在一定的时间间隔里,记录请求次数,当请求次数超过该时间限制时,就把计数器清零,然后重新计算。当请求次数超过间隔内的最大次数时,拒绝访问。计数器算法的实现比较简单,但存在“突刺现象”。突刺现象是指
Stephen
0
985 本硕,秋招上岸阿里算法岗!
↓推荐关注↓节前,我们星球举办了技术&面试交流会,邀请了一些互联网大厂好友以及今年参加社招和校招面试的同学。会上探讨了一系列热门话题,包括大模型发展趋势、算法落地实践、面经总结,以及如何做好面试准备和应对常见考点。基于经验交流与实战经验,我们总结如下:《机器学习算法面试宝典》1.0 发布!今
Python学习与数据挖掘
0
Java版【数据结构与算法】的天花板,收藏好,慢慢看
Java 版数据结构与算法来了,堪称 java 版数据结构与算法的天花板,需要学数据结构与算法的,刷这套就可以了,目录如下,文末附教程地址。基础数据结构-001-二分查找-算法描述基础数据结构-002-二分查找-算法实现基础数据结构-003-二分查找-问题1-循环条件基础数据结构-004-二分查找-
路人甲Java
0
算法工程师的核心竞争力是什么?
点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达链接:https://www.zhihu.com/question/527696166编辑:深度学习与计算机视觉声明:仅做学术分享,侵删作者:赵俊博 Jakehttps://www.zhihu.com/question/52769
小白学视觉
10
我想知道,高德和百度,谁的算法更准?
点击上方牲产力关注我在线提问,平常导航你是用高德还是百度呢?我个人喜欢用百度地图,媳妇儿是用高德,但而且她打车也会直接用高德,我还会再用滴滴来单独打车。总感觉导航嘛,不同软件应该大差不差,没想到一番搜罗还真有些奇奇怪怪的对比。01 大路vs小路江湖传闻,当百度还在大路上给你规划地图时,高德已经给你寻
TTTEED
2
一天肝600多篇文章,用数量对抗算法的不确定性
我写公众号七八年,总原创文章数量也只不过是650多篇。写爆文的一天就干出600多篇,多少有点震惊。背后是公众号平台进行功能调整后,从一天只能发一次文章,变改成了一天可以无限制发任意数量的文章。做公众号爆文写作变现的底层逻辑是基于公众号算法调整,从订阅规则改成了推荐机制,人人都有机会获得系统的推荐流量
python之禅
0
Nat. Commun. | gLM:基于宏基因组预训练语言模型的基因和蛋白调控及功能预测算法
2024年4月3日,Peter R. Girguis、Sergey Ovchinnikov、Yunha Hwang、Andre L. Cornman和Elizabeth H. Kellogg几人在Nature Communications上发表了一篇题为“Genomic language model
生信宝典
0
Nat Biotechnol | 叶凯团队开发基因组新生和体细胞结构变异分析算法—SVision-pro
基因组结构变异与丰富多彩的生物性状进化和严重疾病表型密切相关。多种遗传病和癌症的变异研究需要在多个样本之间进行基因组变异差异比较,进而获得真正与疾病进展相关的新生(de novo)和体细胞(Somatic)结构变异。目前,领域内常用的“先检测再求差”的分步式策略要求在基因组检测后有多个计算步骤,繁杂
生信宝典
0