它是这样实现的： 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
（以上转自维基百科）
下面是我自己的实现，不足之处，还望指正：
代码如下:
// RadixSort.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include
using namespace std;
//定义队列的节点
struct Node
{
int data;
Node* next;
};
//定义程序所需的特殊队列
class Queue
{
public:
Queue()
{
Node* p = new Node;
p->data = NULL;
p->next = NULL;
front = p;
rear = p;
}
~Queue()
{
Node* p = front;
Node* q;
while (p)
{
q = p;
p = p->next;
delete q;
}
}
//在队列的尾部添加一个元素，节点不存在，需要程序创建
void push(int e)
{
Node* p = new Node;
p->data = e;
p->next = NULL;
rear->next = p;
rear = p;
}
//在队列的尾部添加一个节点，节点原来就存在
void push(Node* p)
{
p->next = NULL;
rear->next = p;
rear = p;
}
//数据元素中最大位数
int lenData()
{
int temp(0);//数据元素的最大位数
int n(0); //单个数据元素具有的位数
int d; //用来存储待比较的数据元素
Node* p = front->next;
while (p != NULL)
{
d = p->data;
while (d > 0)
{
d /= 10;
n++;
}
p = p->next;
if (temp < n)
{
temp = n;
}
n = 0;
}
return temp;
}
//判断队列是否为空
bool empty()
{
if (front == rear)
{
return true;
}
return false;
}
//清除队列中的元素
void clear()
{
front->next = NULL;
rear = front;
}
//输出队列中的元素
void print(Queue& que)
{
Node* p = que.front->next;
while (p != NULL)
{
cout data next;
}
}
//基数排序
void RadixSort(Queue& que)
{
//定义一个指针数组，数组中存放十个分别指向十个队列的指针
Queue* arr[10];
for (int i = 0; i < 10; i++)
{
arr[i] = new Queue;
}
int d = 1;
int m = que.lenData(); //取得待排序数据元素中的最大位数
//将初始队列中的元素分配到十个队列中
for(int i = 0; i < m; i++)
{
Node* p = que.front->next;
Node* q;
int k; //余数为k，则存储在arr[k]指向的队列中
while (p != NULL)
{
k = (p->data/d)%10;
q = p->next;
arr[k]->push(p);
p = q;
}
que.clear(); //清空原始队列
//将十个队列中的数据收集到原始队列中
for (int i = 0; i < 10; i++)
{
if (!arr[i]->empty())
{
Node* p = arr[i]->front->next;
Node* q;
while (p != NULL)
{
q = p->next;
que.push(p);
p = q;
}
}
}
for (int i = 0; i < 10; i++)//清空十个队列
{
arr[i]->clear();
}
d *= 10;
}
print(que); //输出队列中排好序的元素
}
private:
Node* front;
Node* rear;
};
int _tmain(int argc, _TCHAR* argv[])
{
Queue oldque;
int i;
cout i)
{
oldque.push(i);
}
oldque.RadixSort(oldque);
cout num%r)/k;
curbox[bn]->next=curn;
curbox[bn]=curbox[bn]->next;
}
curn=headn;
for(i=0;inext=box[i]->next;
curn=curbox[i];
}
}
curn->next=NULL;
}
void printwx()
{
for(curn=headn->next;curn!=NULL;curn=curn->next)
{
coutnum);
}
while(maxn/base>0)
{
maxn/=base;
z++;
}
for(i=0;i