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

Question

要求有：1. 问题描述
2. 设计思路
3. 数据结构定义
4. 系统功能模块介绍
5. 程序清单
6.运行与调试分析

Answer 1

/*
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

Answer 2

你可以判断是否是基数，然后把基数的下标和值用另一个数组来备份。然后再对基数排序，排完之后用下标和值覆盖给定的数组
把题目写具体一点。追问

题目就是基数排序，所以只要和这有关的都行