/*********************\
* 基数排序(桶排序)*
\*********************/
#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
请按任意键继续. . .
分享到:
相关推荐
包括了基数排序的实现代码和流程图。 先对个位数字进行统计,然后根据个位进行排序,然后对十位进行统计,然后根据十位进行排序,即可获得最终结果。 时间效率:待排序列为n个记录,10个关键码,关键码的取值范围为0...
数据结构中的基数排序是一种非比较型整数排序算法,它基于数字的位宽进行排序,尤其适用于处理大量相同数字的情况。基数排序的核心思想是将数字按照位数从低位到高位分别进行桶排序,最终得到完全有序的序列。下面将...
基数排序(Radix Sort)是一种非比较型的整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、卡片等数据(当成是整数即可),所以基数排序并不限于整数。它是...
这里我们将深入探讨四种常见的排序算法:基数排序、堆排序、希尔排序和直接插入排序。 首先,基数排序是一种非比较型整数排序算法,它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在C++中实现基数排序,主要涉及到数组、计数排序以及位操作等技术。以下是关于基数排序及其C++实现的详细解释...
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
基数排序法用链表完成使用C语言适用于刚入门的学者
链式基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在描述中提到的实验报告中,主要目标是实现一个链式基数排序算法,用于对一组数据进行最低位优先的排序...
### Radix Sort (基数排序) 排序算法详解 #### 一、算法介绍与应用场景 基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法对于大数据量的处理非常有效,尤其适合于数据范围远大于内存大小的情况。以下是基数排序的详细...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法非常适合处理大量整数的排序,尤其在数字位数相同或者相差不大的情况下,效率较高。本文将深入...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法适用于处理大量数据,且数据的范围不超过10的某个幂次方的情况。基数排序是基于多关键字排序的一...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,因为其时间复杂度为线性,即O(n*k),其中n是待排序的元素数量,k是每...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序非常有效,尤其是在数据范围不超过0-9的情况下。接下来,我们将深入探讨基数排序...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法不需要进行记录关键字间的比较,而是通过“分配”和“收集”操作对单逻辑关键字进行排序。 1....
### C经典算法之基数排序法 #### 知识点概览 1. **排序算法的基础概念** - 排序算法的基本定义与分类 - 比较性排序与非比较性排序的区别 - 稳定排序与不稳定排序的概念 2. **基数排序的原理** - 分配式排序的...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这个课程设计主要涵盖了基数排序的基本概念、实现方式以及C++编程技术。在本课程设计中,你将学习到如何用...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。它不是基于比较的排序,而是通过创建额外的数据结构,比如计数器或者桶,来达到排序的目的。在处理大量数据时...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,因为它是线性时间复杂度的,即O(nk),其中n是元素数量,k是数字的最大...