基于两两比较的算法，算法的运行下界为Ω（nlogN），如果想再降低时间复杂度，只能通过其他的非基于比较的方法。基数排序就是一种方法，其时间复杂度为O（N）

基数排序的过程，假设有4个数，我们用链表把他们连一起，这4个数为

321  892   538  439

第一步：我们先创建10个链表，L0~L9，然后按4个数的个位的数字，依次接到相应链表的后面

L0 

L1     321

L2     892

L3

L4

L5

L6

L7

L8    538

L9    439

第二步：按连接在链表从L0~L9的数字，我们依照先后顺序，重新生成一个新的链表  

321  892 538 439

然后根据各个数的十位数，我们重新把他们连接到各个链表后面

L0 

L1     

L2     321

L3     538   439

L4

L5

L6

L7

L8    

L9    892

321  538 439 892

然后根据各个数的百位数，我们重新把他们连接到各个链表后面

L0 

L1     

L2     

L3     321

L4     439

L5     538

L6

L7

L8    892

L9   

321  439 538 892

至此，排序结果完成

完整代码如下：

（使用单链表实现的）

#include<iostream>
using namespace std;

typedef  struct Node
{
	int data;
	struct Node *next;
}LNode;

void Initiate(LNode **head)
{
	(*head)=(LNode*)malloc(sizeof(LNode));
	(*head)->next=NULL;
}

void Insert(LNode *head,int num)
{
	if(head==NULL) return;
	else
	{
		LNode *p,*q;
		q=head;
		p=(LNode *)malloc(sizeof(LNode));
		p->data=http://www.mamicode.com/num;>

附上使用双向链表实现的代码：
#include<iostream>
#include<assert.h>
using namespace std;

int power(int a,int n)  //使用递归,O（logn），求a的n次方
{
	int y;
	if(n==0) return 1;
	else 
	{
		y=power(a,n/2);
		y=y*y;
		if(n%2!=0)
			y=a*y;
	}
	return y;
}

typedef struct Node
{
	int key;
	struct Node * prior;
	struct Node * next;
}SLnode;
 
SLnode * create(int n)
{
	SLnode *head,*p,*q;
	int i;
	if((head=(SLnode *) malloc (sizeof(SLnode)))==NULL)
	{
		cout<<"error";
		exit(0);//创建失败则退出
	}
	head->prior=head;
	head->next=head;
	q=head;
	for(i=0;i<n;i++)
	{
		p=(SLnode *) malloc (sizeof(SLnode));
		assert(p!=NULL);//使用断言
		cin>>p->key;
		p->prior=q;
		q->next=p;
		q=p;
	}
	head->prior=q;
	q->next=head;
	return head;
}

void printSL(SLnode *head)
{
	SLnode *p;
	p=head->next;
	while(p!=head)
	{
		cout<<p->key<<"  ";
		p=p->next;

	}
}

SLnode * GetFirstNode(SLnode *head)
{
	SLnode *p;
	p=head->next;
	if(p!=head)
	{
		p->next->prior=p->prior;
		p->prior->next=p->next;
	}
	else p=NULL;
	return p;
}

int get_num(SLnode *p,int i)  //得到第i个数
{
	int key=p->key,num;
	num=key/power(10,i);
	return num%10;
}

void addNode(SLnode *head,SLnode *p)
{
	p->prior=head->prior;
	p->next=head;
	head->prior->next=p;
	head->prior=p;
}

void append(SLnode *head,SLnode *Lhead)
{
	if(Lhead->next!=Lhead)  //这个判断条件一定要写上，
	{
	Lhead->next->prior=head->prior;
	Lhead->prior->next=head;
	head->prior->next=Lhead->next;
	head->prior=Lhead->prior;
	}
}


void radix_sort(SLnode *head,int n)  //实习基数排序
{
	SLnode *Lhead[10],*p;
	int i,j,k,f;
	for(i=0;i<10;i++)
	{
		Lhead[i]=(SLnode *)malloc(sizeof(SLnode));
		assert(Lhead[i]!=NULL);
	}
	
	for(i=0;i<n;i++)
	{
		for(k=0;k<10;k++)
		{
			Lhead[k]->next=Lhead[k];
		    Lhead[k]->prior=Lhead[k];
		}
		while(head->next!=head)
		{
		p=GetFirstNode(head);//get first Node,and delete it
		j=get_num(p,i);//得到第i个数
		addNode(Lhead[j],p);//将取得的节点连接到Lhead[j]后面
		}

	    for(f=0;f<10;f++)
     	  append(head,Lhead[f]);
	}

	 for(i=0;i<10;i++)//删除节点
        delete(Lhead[i]);

}

void main()
{
	int a,b;
	SLnode *head;
	cin>>a;
	head=create(a);
	printSL(head);
	cout<<endl;
	cout<<"weishu"<<endl; //输入所要比较的数字的位数
	cin>>b;
     radix_sort(head,b);
	printSL(head);
	system("pause");
}


基数排序（采用链表）