首页 > 其他 > 详细

排序——基数排序

时间:2014-08-19 12:58:54      阅读:380      评论:0      收藏:0      [点我收藏+]
        基数排序(radix sort)是属于“分配式排序”(distribution sort),基数排序法又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。
排序思想:
        首先按照数据的最低位(个位)将数据分配到0~9十个桶中,然后依次将这些桶中的数据取出来得到按照个位排序后的结果,然后再将排过序的数据按照次低位(十位)将数据分配到0~9十个桶中,依次类推,直到数据都变为有序的序列。
这里举一个简单的例子来说明一下:
假设有数据:12, 23, 22, 14需要排序(这里只用到4个桶,所以只写出两个桶的数据)
第一次:
2: 12, 22     <-----1桶中的数据
3: 23
4: 14
得到排好序的数据为:12, 22, 23, 14
第二次:
1: 12, 14
2: 22, 23
得到排序后的数据为:12, 14, 22, 23
分析:在按个位排完序之后十位相同的数的顺序已经排好了,按照十位排完序之后,百位相同的数据顺序已经排好了。
程序的代码如下:
#include <stdio.h>
#include <malloc.h>
#include <string.h>

void print(int dat[], int len)
{
	int i;

	for(i=0; i < len; i++)
		if(dat[i])	printf("%4d ", dat[i]);
	printf("\n");
}

void radix_sort(int a[], int len)
{
	int *b = (int *)malloc(10*len*sizeof(int)); /*0~9十个桶,这里用一维数组代替二维数组*/;
	int c[10] = {0};
	int i, k, flag;
	int divider = 1;
	
	do
	{
		flag = 0;
		memset(b, 0, 10*len*sizeof(int));
		memset(c, 0, 10*sizeof(int));
		for(i=0; i < len; i++) /*数据全部放入对应的桶中*/
		{
			k = a[i]/divider%10; /*计算当前的数应该放到哪个桶中*/
			if(k)	flag = 1; /*退出循环的条件是所有的数都放到第0个桶中*/
			b[10*k + c[k]++] = a[i];
		}

		for(i=0, k=0; i < 10*len; i++) /*从桶中取出拍好一次序的数据*/
			if(b[i])	a[k++] = b[i];

		printf("中间值:");
		print(a, len);
		divider *= 10; /*按个位排完序之后按十位排,依次类推...*/
	}while(flag);

	free(b);
}

int main()
{
	int a[] = {12, 40, 33, 4, 35, 58, 56, 21, 25, 781, 89, 32, 622};
	
	printf("初始值:");
	print(a, sizeof(a)/sizeof(int));
	radix_sort(a, sizeof(a)/sizeof(int));
	printf("排序后:");
	print(a, sizeof(a)/sizeof(int));
	return 0;
}
程序运行结果截图:
bubuko.com,布布扣
基数排序的特点:

稳定性:稳定

基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于整数的排序,如果我们要把同样的办法运用到浮点数上,我们必须了解浮点数的存储格式,并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻烦的事情,因此,它的使用同样也不多。而且,最重要的是,这样算法也需要较多的存储空间。另外,基数排序(桶排序)在处理多关键字,比如扑克排序(花色有大小,点数也有大小的情况)会使问题变得非常简单。

排序——基数排序,布布扣,bubuko.com

排序——基数排序

原文:http://blog.csdn.net/laoniu_c/article/details/38678481

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!