基数排序算法c语言

① c语言，基数排序

#include <stdio.h>

typedef struct node {
int data;
int next;
} node;

int head; //这里的head是全局变量
int fr[10];
int re[10];

void Distribute(node *a, int w) //第一次w=1
{
int i;
for (i=0; i<10; i++) { //初始化
fr[i] = -1;
}
for (i=head; i!=-1; i=a[i].next) { //第一次i=0
int x = a[i].data / w % 10; //这是以前求一个数各个位的方法例：98%10=8(个位) 98/10%10=9(十位)

if (fr[x] == -1) {
fr[x] = re[x] = i;
}
else {
a[re[x]].next = i;
re[x] = i;
}
}
for (i=0; i<10; i++) {
if (fr[i] != -1) {
a[re[i]].next = -1;
}
}
}

void Collect(node *a)
{
int i, last;

last = -1;
for (i=0; i<10; i++) {
if (fr[i] != -1) {
if (last == -1) {
head = fr[i];
last = re[i];
}
else {
a[last].next = fr[i];
last = re[i];
}
}
}
a[last].next = -1;
}

void Out(node *a, int w)
{
int i, p, k;

printf("weight == %d\n", w);
for (i=0; i<10; i++) {
printf("fr[%d] ", i);
p = fr[i];
k = 0;
while (p != -1) {
printf("->%4d ", a[p].data);
p = a[p].next;
k++;
}
while (k<3) printf("-------"),k++;
printf("-> re[%d]\n", i);
}
}

void Output(node *a, int head) //结构体指针 ，这里的head是形参，调用此函数结束后即释放，不影响全局变量head的值
{
while (head != -1) {
printf("%4d", a[head].data);
head = a[head].next;
}
printf("\n");
}

void main()
{
//对于无数据的数组排序会出错~~~
//614 738 921 485 637 101 215 530 790 306
node a[10]; //结构体数组
int i, n = 10, max;
max = 0x80000000; //此处对0x80000000及MAX的意思不理解
printf("max == %d\n", max);
printf("Please intput %d numbers~\n", n);
for (i=0; i<n; i++) {
scanf("%d", &a[i].data); //赋值
a[i].next = i + 1;
if (a[i].data > max) max=a[i].data;
}
head = 0;
a[n - 1].next = -1;

Output(a, head);
for (i=1; i<=max; i*=10) {
Distribute(a, i);
Out(a, i);
Collect(a);
Output(a, head);
}
}

② 用c语言编写一个排序程序，要求使用基数排序算法，最好能详细解释下，c语言初学者

#include<stdio.h>
#defineMAX_NUM_OF_KEY8//关键字项数的最大值
#defineRADIX10//关键字基数，此时是十进制整数的基数
#defineMAX_SPACE10000
typedefintKeysType;
typedefintInfoType;

typedefstruct
{
KeysTypekeys;//关键字
InfoTypeotheritems;//其它数据项
intnext;
}SLCell;
typedefstruct
{
SLCellr[MAX_SPACE];//静态链表的可利用空间，r[0]为头结点
intkeynum;//记录当前关键字个数
intrecnum;//静态链表的当前长度
}SLList;//静态链表类型

typedefintArrType[RADIX];//指针数组类型

intord(KeysTypekey,intdigitally)
{
inti;

if(digitally)
{//根据位数，返回不同的数位
for(i=0;i<digitally;++i)
{
key/=10;
}
}
returnkey%10;
}


voidDistribute(SLCell*r,inti,ArrTypef,ArrTypee)
{
//静态链表L的r域中记录已按keys[0].....keys[i-1]有序。
//本算法按第i个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同
//f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录
intj,p;

for(j=0;j<RADIX;++j)
{
f[j]=e[j]=0;//初始化指针
}
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys,i);//取得相应数位上的值
if(!f[j])
f[j]=p;//头指针为空，则取得结点位置
else
r[e[j]].next=p;//原来的尾指针指向第i位数相同的新结点
e[j]=p;//尾指指向新结点作为最后结点
}
}

voidCollect(SLCell*r,inti,ArrTypef,ArrTypee)
{
//本算法按keys[i]自小至大地将f[0..radix-1]所指各子表依次链接成一个链表
//e[0..radix-1]为各子有的尾指针
intj,t;

for(j=0;!f[j];++j);//找第一个非空子表
r[0].next=f[j];//r[0].next指向第一个非空结点
t=e[j];
while(j<RADIX-1)
{
for(j=j+1;j<RADIX-1&&!f[j];++j);//找下一个非空子表
if(f[j])
{
r[t].next=f[j];//链接两非空子表
t=e[j];//指向尾结点
}
}
r[t].next=0;//t指向最后一个非空子表中的最后一个结点
}

voidRadixSort(SLList*L)
{
//L是采用静态链表表示的顺序表
//对L作基数排序，使得L成为按关键字自小到大的有序静态链表，
//L.r[0]为头结点
inti;
ArrTypef,e;

for(i=0;i<L->recnum;++i)
{
L->r[i].next=i+1;
}
L->r[L->recnum].next=0;//L改造为静态链表
for(i=0;i<L->keynum;++i)//按最低位优先依次对各关键字进行分配和收集
{
Distribute(L->r,i,f,e);//第i趟分配
Collect(L->r,i,f,e);//第i趟收集
}
}

intmain(void)
{
KeysTypearr[]={69,17,63,32,27,73,49,53},temp;
SLListL;
inti,nLen,nCount;

nCount=0;
nLen=sizeof(arr)/sizeof(KeysType);
L.recnum=nLen;//取得关键字个数
temp=arr[0];
while(temp)
{
temp/=10;
nCount++;
}
L.keynum=nCount;//取得数据位数

for(i=0;i<L.recnum;++i)
{
L.r[i+1].keys=arr[i];//取得元素
}
RadixSort(&L);
for(i=L.r[0].next;i;i=L.r[i].next)
{
printf("%d	",L.r[i].keys);
}
return0;
}

以前学严蔚敏时的代码，当时写了些注释，慢慢看应该能理解。

③ c语言归并排序，基数排序

void merge(int *a, int low, int center, int high){
int m,n,i,j,k;
int *L,*R;
if(low >= high) return;
m = center - low + 1;
n = high - center;
L = (int *)malloc(m * sizeof(int));
R = (int *)malloc(n * sizeof(int));
for(i=0; i<m; ++i) L[i] = a[low+i];
for(i=0; i<n; ++i) R[i] = a[low+i+m];
for(i=0,j=0,k=low; i<m && j<n;++k) {
if(L[i] > R[j])
a[k] = R[j++];
else
a[k] = L[i++];
}
while(i<m) a[k++] = L[i++];
while(j<n) a[k++] = R[j++];
}
void m_sort(int *a, int low, int high){
int center;
if(low < high) {
center = (low + high)/2;
m_sort(a, low, center);
m_sort(a, center+1, high);
merge(a, low, center, high);
}
}
int main(){
int i;
int a[] = {23, 2, 45, 78, 1, 99, 3,65,43,55};
m_sort(a, 0, 6);
for(i=0; i<10; ++i) {
printf("%d ",a[i]);
}
return 0;
}

④ 基数排序是怎么一回事（c语言）

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都是相同。

懂了没？这是网络上的，还不懂的话再问我

⑤ 数据结构===基数排序算法设计/C或者C++

随手写的:
main()
{int count[MAXSIZE], curr, i;
while (scanf("%d", &curr) != EOF) count[curr]++;
for (i = 0; i < MAXSIZE; i++)
if (count[i]) printf("%d %d\n", i, count[i]);
return 0;
}

⑥ 用c语言实现计数排序、基数排序、桶排序算法。

网上找吧,这些都是基本东西,要不买本数据结构的书看看

⑦ c语言，基数排序

如图

//#pragmaGCCdiagnosticerror"-std=c11"
#include<stdlib.h>//有随机数库
#include<malloc.h>
#include<time.h>//用于产生随机数种子
#include<string.h>
#include<stdio.h>

#defineLEN30//要多长这里改就行
intA[LEN];

intascend(constvoid*a,constvoid*b){
return*((int*)a)-*((int*)b);
}

voidprintArr(intA[],intlen){
inti;
for(i=0;i<len;++i){
printf("%d",A[i]);
if((i+1)%10==0)putchar(' ');//10个数换一行
}
}

intmain(){
inti;
srand(time(0));//置随机数种子
printf("生成随机数：↓ ");
for(i=0;i<LEN;++i){
A[i]=rand();
}
printArr(A,LEN);

printf(" 排序后：↓ ");
qsort(A,LEN,sizeof(int),ascend);
printArr(A,LEN);
return0;
}

⑧ 求c语言基数排序与桶排序的源代码

基数排序：

#include<math.h>
testBS()
{
inta[]={2,343,342,1,123,43,4343,433,687,654,3};
int*a_p=a;
//计算数组长度
intsize=sizeof(a)/sizeof(int);
//基数排序
bucketSort3(a_p,size);
//打印排序后结果
inti;
for(i=0;i<size;i++)
{
printf("%d
",a[i]);
}
intt;
scanf("%d",t);
}
//基数排序
voidbucketSort3(int*p,intn)
{
//获取数组中的最大数
intmaxNum=findMaxNum(p,n);
//获取最大数的位数，次数也是再分配的次数。
intloopTimes=getLoopTimes(maxNum);
inti;
//对每一位进行桶分配
for(i=1;i<=loopTimes;i++)
{
sort2(p,n,i);
}
}
//获取数字的位数
intgetLoopTimes(intnum)
{
intcount=1;
inttemp=num/10;
while(temp!=0)
{
count++;
temp=temp/10;
}
returncount;
}
//查询数组中的最大数
intfindMaxNum(int*p,intn)
{
inti;
intmax=0;
for(i=0;i<n;i++)
{
if(*(p+i)>max)
{
max=*(p+i);
}
}
returnmax;
}
//将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
voidsort2(int*p,intn,intloop)
{
//建立一组桶此处的20是预设的根据实际数情况修改
intbuckets[10][20]={};
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum为上式中的1、10、100
inttempNum=(int)pow(10,loop-1);
inti,j;
for(i=0;i<n;i++)
{
introw_index=(*(p+i)/tempNum)%10;
for(j=0;j<20;j++)
{
if(buckets[row_index][j]==NULL)
{
buckets[row_index][j]=*(p+i);
break;
}
}
}
//将桶中的数，倒回到原有数组中
intk=0;
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
if(buckets[i][j]!=NULL)
{
*(p+k)=buckets[i][j];
buckets[i][j]=NULL;
k++;
}
}
}
}

桶排序

#include<stdio.h>
#defineMAXNUM100

voidbucksort(intarr[],intN,intM)
{
intcount[MAXNUM];
for(inti=0;i<=M;i++)
{
count[i]=0;
}

for(inti=0;i<N;i++)
{
++count[arr[i]];
}

for(inti=0;i<=M;i++)
{
for(intj=1;j<=count[i];j++)
{
printf("%d",i);
}
}
}

intmain()
{
inta[]={2,5,6,12,4,8,8,6,7,8,8,10,7,6};
bucksort(a,sizeof(a)/sizeof(a[0]),12);
return0;
}

⑨ 用C语言描述如何实现基数排序。是数据结构课程设计作业

/*
1.基数是利用同位比较的排序算法，时空复杂度都比较低，很适合字母字符串排序
2.比如对int数组用以1和0为基数排序，先比较第一位，0位靠前1位靠后，一直排完32位
3.基数排序不需要特殊的数据结构
4.只需一个函数即能完成基数排序
5.给个邮箱发源码，手机不知道怎么上传附件
6.对于百万级的数据，效率和快速排序相仿，但使用空间低很多，并且在串大小比较方面具有其他排序算法无法匹敌的性能

整理一下代码，终于独立出来了，如果觉得可以就采纳吧
*/

#define elapser

#define debug

//#define descend

#ifndef descend
#define ascend
#endif

#define count_max 0x7fffffff
#define count_min 0x00000002

#define step_default 0x80000000

int radixsort (unsigned int* pdata ,unsigned int count)
{
void radix (unsigned int* pfirst ,unsigned int* plast ,unsigned int step) ;

if (pdata == 0 || count < count_min || count > count_max)
return -1 ;

radix (pdata ,pdata + count - 1 ,step_default) ;

return 0 ;
}

void radix (unsigned int* pfirst ,unsigned int* plast ,unsigned int step)
{
unsigned int* pleft = pfirst ;
unsigned int* pright = plast ;

while (1)
{
#ifdef descend
while ((*pleft & step) && pleft < pright)
#else
while (!(*pleft & step) && pleft < pright)
#endif
pleft++ ;

#ifdef descend
while (!(*pright & step) && pleft < pright)
#else
while ((*pright & step) && pleft < pright)
#endif
pright-- ;

if (pleft >= pright)
break ;

*pleft ^= *pright ;
*pright ^= *pleft ;
*pleft ^= *pright ;

pleft++ ;
pright-- ;
}

if (pleft > pright)
{
pleft-- ;
pright++ ;
}
else
#ifdef descend
if (!(*pleft & step))
#else
if (*pleft & step)
#endif
pleft-- ;
else
pright++ ;

if (!(step >>= 1))
return ;

if (pleft > pfirst)
radix (pfirst ,pleft ,step) ;

if (pright < plast)
radix (pright ,plast ,step) ;

return ;
}

#ifdef debug

#define data_count 1000000

int main ()
{
int radixsort (unsigned int* pdata ,unsigned int count) ;

unsigned int data[data_count] ;

unsigned int* p = data ;
unsigned int* pe = p + data_count ;

srand ((unsigned int) time (0)) ;

while (p < pe)
*p++ = (unsigned int) rand () & 0x0000000f ;

int itime = time (0) ;
int iresult = radixsort (data ,data_count) ;
itime = time (0) - itime ;

for (p = data ; p < pe ; p++)
printf ("%u ," ,*p) ;

printf ("\n") ;

printf ("task was completed in %d seconds while result is %d\n" ,itime ,iresult) ;

printf ("this radixsort routine is made by elapser\nplease choose my anwser if it helps\n") ;

return 0 ;
}

#endif

⑩ 链式基数排序的算法思想（C语言），越多越仔细越好

参考
/* 基数排序的算法源程序*/
#include <stdio.h>
#define D 3 /* D为排序码的最大位数 */
#define R 10 /* R为基数 */
typedef int KeyType;
typedef int DataType;
struct Node; /* 单链表结点类型 */
typedef struct Node RadixNode;
struct Node {
KeyType key[D];
/* DataType info;*/
RadixNode *next;
};
typedef RadixNode * RadixList;
typedef struct QueueNode {
RadixNode *f; /* 队列的头指针 */
RadixNode *e; /* 队列的尾指针 */
} Queue;
Queue queue[R];
void radixSort(RadixList * plist, int d, int r) {
int i,j,k;
RadixNode *p, *head = (*plist)-> next;
for(j = d-1; j > = 0; j--) { /* 进行d次分配和收集*/
p = head;
for(i = 0; i < r; i++) {
queue[i].f = NULL; queue[i].e = NULL; /* 清队列 */
}
while (p != NULL) {
k = p-> key[j]; /* 按排序码的第j个分量进行分配*/
if (queue[k].f == NULL)
queue[k].f = p; /* 若第k个队列为空，则当前记录为队头*/
else (queue[k].e)-> next = p;/* 否则当前记录链接到第k队的队尾*/
queue[k].e = p;
p = p-> next;
}
for(i = 0; queue[i].f == NULL; i++) /* 找出第一个非空队列*/
;
p = queue[i].e; head = queue[i].f; /* head为收集链表的头指针*/
for(i++; i < r; i++)
if(queue[i].f != NULL) { /* 收集非空队列 */
p-> next = queue[i].f;
p = queue[i].e;
}
p-> next = NULL;
}
(*plist)-> next = head;
}
struct Node element[11]={
0,0,0,NULL,/*表头*/
0,3,6,NULL,/*36*/
0,0,5,NULL,/*5*/
0,1,6,NULL,/*16*/
0,9,8,NULL,/*98*/
0,9,5,NULL,/*95*/
0,4,7,NULL,/*47*/
0,3,2,NULL,/*32*/
0,3,6,NULL,/*36*/
0,4,8,NULL,/*48*/
0,1,0,NULL /*10*/
};
int main(){
int i;
RadixList p = element;
for (i = 0; i < 10; i++)
element[i].next = &element[i+1];
element[10].next = NULL;
radixSort(&p, 3, 10);
p = p-> next;
while (p != NULL){
printf( "%d ", p-> key[1]*10+p-> key[2]);
p = p-> next;
}
getchar();
return 0;
}