开发者社区> tengweitw> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【算法导论】基数排序

简介: 基数排序 时间复杂度:O(n). 基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。
+关注继续查看

基数排序

时间复杂度:O(n).

基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。而基数排序则是先比较低位,再比较高位。通过各个位的比较进行排序,如果数组元素最大有N位,则总共需要N次排序。注意:按位排序必须是稳定排序,所以在这我选择了计数排序。具体操作见下图:

具体实现如下
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

void CountSort(int* arrayA,int* arrayD,int n,int k);
void RadixSort(int* arrayA,int n);

void main()
{
	int arrayD[]={1046,2084,9046,12074,56,7026,8099,17059,33,1};
	int n=sizeof(arrayD)/sizeof(int);
	RadixSort(arrayD,n);

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

}

/****************************************\
函数功能:进行非比较的计数排序
输入:数组D为原始数组
输出:无
\****************************************/
void RadixSort(int* arrayD,int n)
{
	int base=1;//用于取出各个位
	int* arrayA=(int*)malloc(sizeof(int)*n);
	for(int k=0;k<5;k++)//这里的5由原始数组最大数据位数确定
	{	
		base*=10;
		for(int i=0;i<n;i++)//这里用来取各个位上的数
		{
			arrayA[i]=arrayD[i]%base;
			arrayA[i]/=base/10;
		}
		CountSort(arrayA,arrayD,n,10);
	}
	free(arrayA);//记得释放空间
}

/****************************************\
函数功能:进行非比较的计数排序
输入:数组A、D,D为原始数组
输出:无
\****************************************/
void CountSort(int* arrayA,int*arrayD,int n,int k)
{
	int* arrayB=(int*)malloc(sizeof(int)*n);
	int* arrayC=(int*)malloc(sizeof(int)*k);

	for(int i=0;i<=k;i++)
		arrayC[i]=0;//数组C初始化
	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]=arrayD[j];
		arrayC[arrayA[j]]=arrayC[arrayA[j]]-1;//进行计数排序
	}
	for(int i=0;i<n;i++)
	{
		arrayD[i]=arrayB[i];
	}
}

注意:我是在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);
} 


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

相关文章
【算法导论】插入排序
没办法就是这么没原则,又开了个坑。每天看点书,不管什么书。 1. 需求:   输入:n个数的一个序列(a1, a2,  a3……an)   输出: 输出序列的一个排列(a1', a2', a3' ……an'),满足a1'
961 0
《算法导论(原书第3版)》一2.1 插入排序
本节书摘来自华章出版社《算法导论(原书第3版)》一 书中的第2章,第2.1节,作者:(美)Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1089 0
【算法导论】桶排序
桶排序 时间复杂度为:O(n) 基本思想:将要排列的序列分成n组,每组分别进行排序,然后在合并到一起,这里面有分而治之的思想。实例说明:大家学c语言肯定学过switch-case结构,最常见的题型就是对成绩进行分类,但是这里我们是对其进行排名。
857 0
【算法导论】排序算法总结
排序算法总结         从六月初开始看算法导论,陆陆续续看了有2个月了,但实际看的时间只有半个月左右。这期间都忙着找导师、期末考试,同时还回家修养了十来天。
1109 0
【算法导论】计数排序
计数排序 比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。 常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。
802 0
【算法导论】快速排序
快速排序         快速排序的最坏运行时间为O(n2),虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为O(nlogn),并且O(nlogn)中的隐含常数因子很小。
683 0
【算法导论】堆排序
        堆排序像合并排序一样,时间复杂度为O(nlogn);像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。         二叉堆的概念:是一种数组对象,可以被视为一棵完全二叉树,树的每一层都是填满的,最后一层可能除外。
763 0
【算法导论】插入排序法
插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些。在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数;在最差情况下,即输入数组是逆序排列时,时间复杂度为.
750 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
文章
问答
文章排行榜
最热
最新
相关电子书
更多
面试常考算法
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载