内部排序[5]计数排序、基数排序和桶排序

2018年01月13日 09:01 | 704次浏览

前言

    最后三种排序算法了,由于都不是基于比较的排序,因此这三种排序算法可以以线性时间运行。但是因为限制条件的特殊性,因此应用面没有基于元素比较的排序算法广,但是在很多特定的情况下还是蛮有用途的,而且效率极高。


计数排序

    计数排序是建立在这样的前提条件下的:假设n个输入元素的每一个都是0到k区间内的一个整数,其中k为某个整数。因此我们后面所写的程序也只是针对0到k之间的元素进行排序,换句话说,排序元素中不能有负数。


    计数排序的基本思想是:对一个输入元素x,先确定所有输入元素中小于x的元素个数,那么排序后x所在的位置也就明确了。比如,所有的输入元素中有10个元素小于x,那么排好序后x的位置序号就应该是11。当然,如果有相同元素,自然要放到相邻的位置上。


    算法导论上给出了计数排序的很详细的伪代码,我们根据此伪代码,并设数组arr为输入数组,arr中的每个元素值在0到k之间,brr为排序后的输出数组,crr记录arr中每个元素出现的次数。写出代码如下:

/*
第一种形式实现计数排序
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组,每个元素均是0-k中的一个值
brr[0...len-1]为排序后的输出数组
crr[0...k]保存0...k中每个值在数组arr中出现的次数
*/
void Count_Sort(int *arr,int *brr,int *crr,int len,int k)
{
	int i,j=0;
	//数组crr各元素置0
	for(i=0;i<=k;i++)
		crr[i] = 0;
	//统计数组arr中每个元素重复出现的个数
	for(i=0;i<len;i++)
		crr[arr[i]]++;
	//求数组arr中小于等于i的元素个数
	for(i=1;i<=k;i++)
		crr[i] += crr[i-1];
	//把arr中的元素放在brr中对应的位置上
	for(i=len-1;i>=0;i--)
	{
		brr[crr[arr[i]]-1] = arr[i];
		//如果有相同的元素,则放在下一个位置上
		crr[arr[i]]--;
	}
}

 很明显上面代码的时间复杂度为O(n+k),但用到了brr来保存排序结果,我们可以它做些改进,使排序原地进行,如下:

/*
第二种形式实现计数排序
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组,每个元素均是0-k中的一个值
crr[0...k]保存0...k中每个值在数组arr中出现的次数
*/
void Count_Sort(int *arr,int *crr,int len,int k)
{
	int i,j=0;
	//数组crr各元素置0
	for(i=0;i<=k;i++)
		crr[i] = 0;
	//统计数组arr中每个元素重复出现的个数
	for(i=0;i<len;i++)
		crr[arr[i]]++;
	//根据crr[i]的大小,将元素i放入arr适当的位置
	for(i=0;i<=k;i++)
		while((crr[i]--)>0)
		{
			arr[j++] = i;
		}
}

采用如下代码测试:

int main()
{
	int i; 
	//待排序数组,每个元素均在0-8之间
	int arr[] = {2,1,3,8,6,0};
	int brr[6];
	int crr[9];
	Count_Sort(arr,brr,crr,6,8);
	printf("计数排序后的结果为:");
	for(i=0;i<6;i++)
		printf("%d ",brr[i]);
	printf("\n");
	return 0;
}

 测试结果如下:

 最后我们稍微总结下计数排序的特点:


    1、不是基于比较的排序,因此可以达到线性排序时间;


    2、采取空间换时间的思想,需要brr和crr等辅助空间,但是时间复杂度仅为O(n+k);


    3、稳定性好,这也是计数排序最重要的一个特性。


    在实际工作中,当k=O(n)时,我们一般才会采取计数排序,如果k很大,则不宜采取该算法,尤其在如下情形下:


待排序元素为:1、3、8、5、10000000,这样会造成很大的资源浪费。


基数排序

    基数排序的排序时间也可以达到线性,尤其在k和d(后面介绍该参数)很小的情况下。

    基数排序采取的是多关键字比较的策略,且每个关键字对排序的影响不同,根据关键字影响的主次,有两种排序方法:

    1、先根据影响最大的关键字来排序,而后在该关键字相同的情况下,再根据影响次之的关键字来排序,依此类推,直到最后按照影响最小的关键字排序后,序列有序。我们称这个为先高位后低位。


    2、先根据影响最小的关键字来排序,而后再对全部的元素根据影响次小的关键字来排序,依此类推,直到最后按照影响最大的关键字排序后,序列有序。我们称这个为先低位后高位。


    这有点抽象,我们用具体的例子来说明。比如,我们希望用三个关键字(年、月、日)来对日期进行排序,按照基数排序的思想,则:


    采取第一种方法排序的思路是这样的:先比较年,形成一个按照年有序排列的序列,而后对年相等的日期,在比较月,对月相等的日期,再比较日,最后得到有序序列。


    采取第二种方法排序的思路是这样的:先对所有元素按照日排序,再对所有元素按照月排序,最后对所有元素按照年排序,得到有序序列。


    我们一般采用第二种方法来进行排序,比如如下的数字序列:

217,125,362,136,733,522

先对个位上的数字进行排序,得到:

362,522,733,125,136,217

再对十位上的数字进行排序,得到:

217,522,125,733,136,362


    最后对百位上的数字进行排序,得到:

125,136,217,362,522,733


    很明显,高位数字比低位数字对排序的影响大,该方法的正确性很容易证明,这里不再说明。

    我们注意到,这里每一步都需要对各个位上的数进行排序。而为了保证基数排序的正确性(稳定性),我们对每个位上的数进行排序时可以选用计数排序。算法导论上给的伪代码太粗略了,直接贴出自己写的完全代码(包括测试代码),如下:

/*******************************
		  基数排序

********************************/
#include<stdio.h>
#include<stdlib.h>

/*
在第一种计数排序的实现形式上做了些修改
计数排序后的顺序为从小到大
arr[0...len-1]为待排数组,我们这里采用三位数
brr[0...len-1]为排序后的有序数组
w[0...len-1]用来保存取出的每一位上的数,其每个元素均是0-k中的一个值
crr[0...k]保存0...k中每个值出现的次数
*/
void Count_Sort(int *arr,int *brr,int *w,int *crr,int len,int k)
{
	int i;
	//数组crr各元素置0
	for(i=0;i<=k;i++)
		crr[i] = 0;
	//统计数组w中每个元素重复出现的个数
	for(i=0;i<len;i++)
		crr[w[i]]++;
	//求数组w中小于等于i的元素个数
	for(i=1;i<=k;i++)
		crr[i] += crr[i-1];
	//把arr中的元素放在brr中对应的位置上
	for(i=len-1;i>=0;i--)
	{
		brr[crr[w[i]]-1] = arr[i];
		//如果有相同的元素,则放在下一个位置上
		crr[w[i]]--;
	}
	//再将brr中的元素复制给arr,这样arr就有序了
	for(i=0;i<len;i++)
	{
		arr[i] = brr[i];
	}
}

/*
基数排序后的顺序为从小到大
其中参数d为元素的位数
*/
void Basic_Sort(int *arr,int *brr,int *w,int *crr,int len,int k,int d)
{
	int i,j,val=1;
	//从低位到高位依次进行计数排序
	for(i=1;i<=d;i++)
	{	//w中保存的是arr中每个元素对应位上的数
		//范围在0-k之间
		for(j=0;j<len;j++)
			w[j] = (arr[j]/val)%10;	
		//对当前位进行计数排序
		Count_Sort(arr,brr,w,crr,len,k);
		val *= 10;
	}
}

int main()
{
	int i; 
	//待排序数组,每个元素的每一位均在0-7之间
	int arr[] = {217,125,362,136,733,522};
	int brr[6];	//用来保存每次计数排序后的结果
	int w[6];	//每次循环时,保存该位上的数
	int crr[8];	//每次循环时,保存该位上的数出现的次数
	Basic_Sort(arr,brr,w,crr,6,7,3);
	printf("计数排序后的结果为:");
	for(i=0;i<6;i++)
		printf("%d ",arr[i]);
	printf("\n");
	return 0;
}

测试结果如下:

最后我们同样对基数排序稍微做下总结:

    1、同样不是基于比较的排序,因此可以达到线性排序时间;

    2、同样采取空间换时间的思想,需要额外的辅助空间,但是时间复杂度仅为O(d(n+k));

    3、基数排序的稳定性同样也很好。


    吐槽一下:写Basic_Sort的时候,每一次的val应该是10的i-1次方,手误,打成了10*(i-1), 跟踪调试了一下午,每次循环w数组中的值都是个位数,就在那几行代码找问题,但尼玛我偏偏就是没看出来。


桶排序

    桶排序假设输入数据服从均匀分布,平均情况下它的时间复杂度为O(n)。与计数排序类似,因为对输入数据作了某种假设,桶排序的速度也很快。

    桶排序将输入元素按照一定的区间划分为若干个桶,因为假设了输入的数据在总的区间范围内是均匀分布的,因此一般不会出现很多个元素落在同一个桶中的情况。我们可以先对每个桶中的元素排序,而后按照桶的序号,依次把各个桶中的元素列出来即可。


    在进行桶排序时,我们需要一个辅助数组来存放每个桶,而每个桶中的元素最好用链表串起来,这样操作起来比较方便。一个很普遍的展示图例如下:

 桶排序了解思想即可,代码我们就不再实现了,因为它的实现不具备普遍性,要根据不同的情况来划分不同个数的桶,以及桶所规定的区间。

    2014校招时创新工厂下的涂鸦移动有一道这样的面试题:

   一个字符数组,里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序,要求所有小写字符放在最前面,所有大写字符放在中间,所有数字放在最后。而且各部分内部分别有序。

    这个很明显用桶排序来实现效果最佳,尤其在数据量非常大的情况下。

   再比如,如下情况也是用桶排序的最佳时机(摘自百度百科)

海量数据

一年的全国高考考生人数为500 万,分数使用标准分,最低100 ,最高900 ,没有小数,你把这500 万元素的数组排个序。

分析:对500W数据排序,如果基于比较的先进排序,平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现,这些数据都有特殊的条件: 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。

方法:创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出,即可以得到一个有序的序列。而且可以很容易的得到100分有***人,501分有***人。

实际上,桶排序对数据的条件有特殊要求,如果上面的分数不是从100-900,而是从0-2亿,那么分配2亿个桶显然是不可能的。所以桶排序有其局限性,适合元素值集合并不大的情况。



感觉本站内容不错,读后有收获?小额赞助,鼓励网站分享出更好的教程


上一篇:sql 表连接 下一篇:hive视图和索引
^