【算法导论】计数排序-阿里云开发者社区

开发者社区> tengweitw> 正文

【算法导论】计数排序

简介: 计数排序 比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。 常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。
+关注继续查看
计数排序

比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。

常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。任何比较排序法在最坏情况下的时间复杂度为O(nlogn)。因此,合并排序和堆排序是渐进最优的

非比较排序:用非比较的方法来进行排序的算法。

常见的非比较排序算法有:计数排序法、基数排序法、桶排序法。它们都是以线性时间运行的。由于是非比较的,因此下界O(nlogn)对它们是不适用的。

下面来讨论计数排序

前提假设:序列的值域在0到k之间。

时间复杂度:O(n)

基本思想:对于序列中的每一个元素,计算得到小于该元素的元素个数,从而确定了该元素在最终输出元素的位置。

从下图中可以了解算法的过程(其中A数组是原始序列,B数组为最终序列,C数组为临时辅助序列。):


:黑色方框看不清不要紧,代表的是B数组还没有填充的空间。

具体的实现如下:


#include<stdio.h>

void CountSort(int* arrayA,int* arrayB,int* arrayC,int n,int k);

void main()
{
	int arrayA[8]={2,5,3,0,2,3,0,3};
	int arrayB[8]={0};
	int n=sizeof(arrayA)/sizeof(int);
	int k=5;//k为数组中的最大值
	int arrayC[6]={0};

	CountSort(arrayA,arrayB,arrayC,n,k);

	for(int i=0;i<n;i++)
		printf("%d ",arrayB[i]);
	printf("\n");
}

/****************************************\
函数功能:进行非比较的计数排序
输入:数组A、B、C(注意A B长度相同,与C不一定相同)
输出:无
\****************************************/
void CountSort(int* arrayA,int* arrayB,int* arrayC,int n,int k)
{
	for(int i=0;i<=k;i++)
		arrayC[i]=0;
	for(int j=0;j<n;j++)
		arrayC[arrayA[j]]=arrayC[arrayA[j]]+1;
	for(int i=1;i<=k;i++)
		arrayC[i]=arrayC[i]+arrayC[i-1];
	
	for(int j=n-1;j>=0;j--)
	{
		arrayB[arrayC[arrayA[j]]-1]=arrayA[j];
		arrayC[arrayA[j]]=arrayC[arrayA[j]]-1;
	}

}

注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为:

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
} 


原文:http://blog.csdn.net/tengweitw/article/details/9629567

作者:nineheadedbird


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【算法导论】选择排序法
选择排序法         选择排序其实是冒泡法的一种改进,其基本思路也是:先确定最小元素,再找次最小元素,最后确定最大元素。         它与冒泡排序的最大区别在于:冒泡排序是只要碰见比它大的元素就交换,而选择排序是直接将元素放在最终的确定位置,从而避免了多次交换过程。
934 0
看动画学算法之:排序-基数排序
之前的文章我们讲了count排序,但是count排序有个限制,因为count数组是有限的,如果数组中的元素范围过大,使用count排序是不现实的,其时间复杂度会膨胀。 而解决大范围的元素排序的办法就是基数排序。
783 0
【算法导论】桶排序
桶排序 时间复杂度为:O(n) 基本思想:将要排列的序列分成n组,每组分别进行排序,然后在合并到一起,这里面有分而治之的思想。实例说明:大家学c语言肯定学过switch-case结构,最常见的题型就是对成绩进行分类,但是这里我们是对其进行排名。
892 0
《计算机科学与工程导论:基于IoT和机器人的可视化编程实践方法第2版》一1.1.1 计算机科学和工程的课程体系
本节书摘来华章计算机《计算机科学与工程导论:基于IoT和机器人的可视化编程实践方法第2版》一书中的第1章 ,第1.1.1节,陈以农 陈文智 韩德强 著 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
972 0
《计算机科学与工程导论:基于IoT和机器人的可视化编程实践方法第2版》一1.1.2 计算机就业形势分析
本节书摘来华章计算机《计算机科学与工程导论:基于IoT和机器人的可视化编程实践方法第2版》一书中的第1章 ,第1.1.2节,陈以农 陈文智 韩德强 著 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
845 0
【算法导论】合并排序法
       分治法:将原问题划分为n个规模较小而结构与原问题相似的子问题;递归地解决这些子问题,然后再合并其结果,就得到了原问题的解。分治法在每一个递归上都有三个步骤:分解、解决、合并。
784 0
闰年的算法
关于平年、闰年的算法,大家比较耳熟的可能就是“四年一闰”的说法,但实际上这个说法是不准确的。看看天文学上关于平年闰年的规定就很清楚了: 天文学上,把地球绕太阳一周称为一年。但实际上,地球绕太阳转一圈需要365天5时48分46秒,也就是365.2422天,为了方便,一年定为365天,叫做平年;这样每过四年差不多就要多出一天来,把这一天加在2月里,这一年就有366天,叫做闰年。
1134 0
【算法导论】基数排序
基数排序 时间复杂度:O(n). 基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。
807 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
159
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载