学步园

     基数排序是个很有特点的排序方法。它不关注整个数据，而是数据的每一位。按每一位排完序之后，最终的排序序列也就出来了。

#include <iostream>
using namespace std;

const int Max = 1000+1;	//列表的最大元素个数
const int Radix = 10;	//基数
const int KeyNum = 10;	//每个元素的最大位数

typedef int KeyType; //排序的元素的类型

typedef struct node
{
	KeyType data[KeyNum];	//将待排数的每个位存在数组中
	KeyType wholeData;	//待排数据整个存储
	int next;	//指针域
}SLListElem; //静态链表数据元素

typedef struct list
{
	SLListElem s[Max];	//0号元素作为头结点，不存数据，指针域仅记录第一个元素的位置
	int size;
}SLList;	//静态链表

//输入
void input(SLList &L)
{
	int num, index;

	for(int i=0; i<Max; i++) L.s[i].next = 0; //

	index = 0;
	while(cin >> num && num != 0)
	{
		index ++;
		for(int i=0; i<KeyNum; i++) L.s[index].data[i] = 0;	//

		L.s[index].wholeData = num;

		//将待排的数据元素分割
		for(int i=0; num; i++)
		{
			L.s[index].data[i] = (num % Radix);
			num /= Radix;
		}
		
		//前插法建立静态链表
		L.s[index].next = L.s[0].next;
		L.s[0].next = index;
	}

	L.size = index;
}

//将数据分割到每个子表中
void distribute(SLList &L, int head[Radix], int tail[Radix], int seq)
{
	for(int i=0; i<KeyNum; i++) head[i] = 0;

	//！！！！得按静态链表的顺序处理元素！
	//遍历静态链表时，很容易习惯上的按照下标来遍历链表
	for(int i=L.s[0].next; i; i=L.s[i].next)
	{
		int pos = L.s[i].data[seq];

		if(!head[pos])
		{
			head[pos] = i;
		}
		else
		{
			L.s[tail[pos]].next = i;
		}

		tail[pos] = i;	//尾指针跟上
	}
}

//合并各个子表
void collect(SLList &L, int head[Radix], int tail[Radix], int seq)
{
	int index, t;
	//找到第一个非空子表
	for(index=0; index<Radix && !head[index]; index++);

	L.s[0].next = head[index];
	t = tail[index];

	index ++; //指向下一链表
	while(index < Radix)
	{
		//找到下一个非空子表
		for(; index < Radix-1 && !head[index]; index++);

		if(head[index])
		{
			L.s[t].next = head[index];
			t = tail[index];
		}
		index ++;
	}
	L.s[t].next = 0;	//静态链表封尾
}

//基数排序
void radixSort(SLList &L)
{
	int head[Radix], tail[Radix];

	for(int i=0; i<KeyNum; i++)
	{
		distribute(L, head, tail, i);
		collect(L, head, tail, i);
	}
}

//输出排序后结果
void output(SLList L)
{
	int pointer;

	pointer = L.s[0].next;
	while(pointer)
	{
		cout << L.s[pointer].wholeData << ' ';
		pointer = L.s[pointer].next;
	}
}

int main()
{
	SLList L;
	input(L);
	radixSort(L);
	output(L);
	system("pause");
	return 0;
}

     我拿来测试的一组数据：

      278 109 63 930 589 184 505 269 8 83 0