/*********************\
* 基数排序(桶排序)*
\*********************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
//struct of node
typedef struct node{
int num;
struct node * next;
}NODE;
/*!<链表尾部添加节点*/
void addnode(NODE * head,int num)
{
NODE * temp = head;
while(temp->next)temp=temp->next;
NODE * newnode = (NODE*)malloc(sizeof(NODE));
newnode->next = NULL;
newnode->num = num;
temp->next=newnode;
}
/*!<释放所有链表空间*/
void freelist(NODE * head)
{
NODE * temp;
while(head)
{
temp = head;
head = head->next;
free(temp);
}
}
/*!<清空链表,只留表头*/
void clearlist(NODE * head)
{
NODE * p = head->next;
NODE * q;
head->next = NULL;
while(p)
{
q = p;
p = p->next;
free(q);
}
}
/*!<打印链表数据*/
void printlist(NODE * head)
{
NODE * temp = head->next;
while(temp)
{
printf("->%d",temp->num);
temp=temp->next;
}
putchar('\n');
}
/*!<基数排序函数*/
void RadixSort(int a[],int bass,int n)
{
int max = 0,i,j,k=0,iTemp,sort_times;
NODE ** barrel;
//确定排序趟数
for(i=0;i<n;i++)
if(a[i]>max)max=a[i];
for(sort_times=0;pow(bass,sort_times)<max;sort_times++);
barrel = (NODE**)malloc(bass*sizeof(NODE*));
//初始化桶
for(i=0;i<bass;i++)
{
NODE * node = (NODE*)malloc(sizeof(NODE));
node->next = NULL;
barrel[i]=node;
}
//排序
for(i=0;i<sort_times;i++)
{
for(j=0;j<n;j++)
{
iTemp = a[j]%(int)round(pow(bass,i+1));
iTemp = iTemp/(int)round(pow(bass,i));
addnode(barrel[iTemp],a[j]);
}
//打印桶内数据
printf("第 %d 趟排序桶内数据情况:\n",i);
for(j=0;j<bass;j++)
{
printf("barrel[%d]",j);
printlist(barrel[j]);
}
for(j=0,k=0;j<bass;j++)
{
NODE * temp=barrel[j]->next;
while(temp)
{
a[k++]=temp->num;
temp=temp->next;
if(k>n) break;
}
}
//打印每趟排序后的结果
printf("第 %d 趟排序后队列情况:\n",i);
for(j=0;j<n;j++)
{
printf("%d ",a[j]);
}
putchar('\n');
//清空桶
for(j=0;j<bass;j++) clearlist(barrel[j]);
}
//释放空间
for(i=0;i<bass;i++) freelist(barrel[i]);
}
/*!< func main*/
int main(void)
{
int i = 0,n,bass;
int a[] = {1,6,2,8,3,25,66,7,3,5,634,633,643,2465,2355,2120};
n=sizeof(a)/sizeof(int);
printf("请输入基数排序的基数:\n");
scanf("%d",&bass);
printf("--排序前--: \n");
for(i=0;i<n;i++) printf(" %d ",a[i]);
putchar('\n');
RadixSort(a,bass,n);
printf("--排序后--: \n");
for(i=0;i<n;i++)printf(" %d ",a[i]);
putchar('\n');
system("pause");
return 0;
}
执行情况:
请输入基数排序的基数:
10
--排序前--:
1 6 2 8 3 25 66 7 3 5 634 633 643 2465 2355 2120
第 0 趟排序桶内数据情况:
barrel[0]->2120
barrel[1]->1
barrel[2]->2
barrel[3]->3->3->633->643
barrel[4]->634
barrel[5]->25->5->2465->2355
barrel[6]->6->66
barrel[7]->7
barrel[8]->8
barrel[9]
第 0 趟排序后队列情况:
2120 1 2 3 3 633 643 634 25 5 2465 2355 6 66 7 8
第 1 趟排序桶内数据情况:
barrel[0]->1->2->3->3->5->6->7->8
barrel[1]
barrel[2]->2120->25
barrel[3]->633->634
barrel[4]->643
barrel[5]->2355
barrel[6]->2465->66
barrel[7]
barrel[8]
barrel[9]
第 1 趟排序后队列情况:
1 2 3 3 5 6 7 8 2120 25 633 634 643 2355 2465 66
第 2 趟排序桶内数据情况:
barrel[0]->1->2->3->3->5->6->7->8->25->66
barrel[1]->2120
barrel[2]
barrel[3]->2355
barrel[4]->2465
barrel[5]
barrel[6]->633->634->643
barrel[7]
barrel[8]
barrel[9]
第 2 趟排序后队列情况:
1 2 3 3 5 6 7 8 25 66 2120 2355 2465 633 634 643
第 3 趟排序桶内数据情况:
barrel[0]->1->2->3->3->5->6->7->8->25->66->633->634->643
barrel[1]
barrel[2]->2120->2355->2465
barrel[3]
barrel[4]
barrel[5]
barrel[6]
barrel[7]
barrel[8]
barrel[9]
第 3 趟排序后队列情况:
1 2 3 3 5 6 7 8 25 66 633 634 643 2120 2355 2465
--排序后--:
1 2 3 3 5 6 7 8 25 66 633 634 643 2120 2355 2465
请按任意键继续. . .
分享到:
相关推荐
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、日期等,基数排序并不限于整数。基数排序的名称来源...
基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于...
在计算机科学中,基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、浮点数等,基数排序也不是只能用于...
基数排序是一种非比较型的整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如名字或日期)和特定格式的浮点数,所以基数排序并不限于整数。基数排序算法...
### Python简单实现基数排序算法 #### 一、引言 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较排序。与传统的比较排序不同,基数排序适用于特定类型的数据集...
基数排序(Radix sort)是一种非比较型整数排序算法,它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方式特别适合处理大数据量且数据范围较小的情况。在C#中,我们可以使用以下方法...
基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,因为它可以避免大量的比较操作,而是通过计数和分配来完成排序。 ...
基数排序算法是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。具体实现时,从最低位开始,也就是个位数,然后是十位、百位等等,直到最高位。在每一趟排序中,使用的是...
本文将详细讲解Java中的基数排序,这是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序对于大数据量的整数排序具有很高的效率,尤其适用于处理多位数的数组。 ...
平日所见的基数排序基本都是讲正整数的,没有讲到负数的,所以今天写一个可解决负数情况的基数排序。 首先,我们可以加上某个值,使得数组中肯定不会出现负数,然后这样我们就可以按照以前基数排序的套路进行排序了...
链式基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在描述中提到的实验报告中,主要目标是实现一个链式基数排序算法,用于对一组数据进行最低位优先的排序...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、日期等,所以基数排序并不是只能用于整数。 基数排序的Java实现方法RadixSort,...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。通常用于整数排序,它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别比较。具体的排序方式是...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,尤其是在数值范围较大的情况下。在Linux系统,特别是Ubuntu 13.04这样...