• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

c++(基数排序)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

    基数排序是另外一种比较有特色的排序方式,它是怎么排序的呢?我们可以按照下面的一组数字做出说明:12、 104、 13、 7、 9

    (1)按个位数排序是12、13、104、7、9

    (2)再根据十位排序104、7、9、12、13

    (3)再根据百位排序7、9、12、13、104

    这里注意,如果在某一位的数字相同,那么排序结果要根据上一轮的数组确定,举个例子来说:07和09在十分位都是0,但是上一轮排序的时候09是排在07后面的;同样举一个例子,12和13在十分位都是1,但是由于上一轮12是排在13前面,所以在十分位排序的时候,12也要排在13前面。

    所以,一般来说,10基数排序的算法应该是这样的?

    (1)判断数据在各位的大小,排列数据;

    (2)根据1的结果,判断数据在十分位的大小,排列数据。如果数据在这个位置的余数相同,那么数据之间的顺序根据上一轮的排列顺序确定;

    (3)依次类推,继续判断数据在百分位、千分位......上面的数据重新排序,直到所有的数据在某一分位上数据都为0。

    说了这么多,写上我们的代码。也希望大家自己可以试一试。

    a)计算在某一分位上的数据

 

int pre_process_data(int array[], int length, int weight)
{
	int index ;
	int value = 1;

	for(index = 0; index < weight; index++)
		value *= 10;

	for(index = 0; index < length; index ++)
		array[index] = array[index] % value /(value /10);

	for(index = 0; index < length; index ++)
		if(0 != array[index])
			return 1;

	return 0;
}
    b)对某一分位上的数据按照0~10排序

 

void sort_for_basic_number(int array[], int length, int swap[])
{
	int index;
	int basic;
	int total = 0;

	for(basic = -9; basic < 10; basic++){
		for(index = 0; index < length; index++){
			if(-10 != array[index] && basic == array[index] ){
				swap[total ++] = array[index];
				array[index] = -10;
			}
		}
	}

	memmove(array, swap, sizeof(int) * length);
}

 


    c)根据b中的排序结果,对实际的数据进行排序

 

void sort_data_by_basic_number(int array[], int data[], int swap[], int length, int weight)
{
	int index ;
	int outer;
	int inner;
	int value = 1;

	for(index = 0; index < weight; index++)
		value *= 10;

	for(outer = 0; outer < length; outer++){
		for(inner = 0; inner < length; inner++){
			if(-10 != array[inner] && data[outer]==(array[inner] % value /(value/10))){
				swap[outer] = array[inner];
				array[inner] = -10;
				break;
			}
		}
	}

	memmove(array, swap, sizeof(int) * length);
	return;
}

 

    d)把a、b、c组合起来构成基数排序,直到某一分位上的数据为0

 

 

void radix_sort(int array[], int length)
{
	int* pData;
	int weight = 1;
	int count;
	int* swap;
	if(NULL == array || 0 == length)
		return;

	pData = (int*)malloc(sizeof(int) * length);
	assert(NULL != pData);
	memmove(pData, array, length * sizeof(int));

	swap = (int*)malloc(sizeof(int) * length);
	assert(NULL != swap);

	while(1){
		count = pre_process_data(pData, length, weight);
		if(!count)
			break;

		sort_for_basic_number(pData, length, swap);
		sort_data_by_basic_number(array, pData, swap, length, weight);
		memmove(pData, array, length * sizeof(int));
		weight ++;
	}

	free(pData);
	free(swap);
	return;
}

 

 

总结:

    (1)测试的时候注意负数的情形

    (2)如果在某一位数据相同,那么需要考虑上一轮数据排序的情况

    (3)代码中多次分配小空间,此处代码待优化

 

补充:

    (1) 10月15日晚上修改了余数取值范围,这样负数也可以参加排序

    (2)10月16日上午增加了一个swap内存分配,避免了内存的重复分配和释放

    (3)10月16日上午删除了count计数,一旦发现有不等于0的数据直接返回为1,不需要全部遍历数据

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#Redis使用发布时间:2022-07-14
下一篇:
2020数学建模C国一论文,方向是金融数据挖掘发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap