【转】基数排序(链表运用)

只看该作者 · 2017-1-5 12:34

基于两两比较的算法，算法的运行下界为Ω（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

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

321 538 439 892

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

L0

L1

L2

L3 321

L4 439

L5 538

L6

L7

L8 892

L9

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

321 439 538 892

至此，排序结果完成

完整代码如下：

（使用单链表实现的）

[cpp] view plain copy

#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=num;
p->next=NULL;
while(q->next!=NULL)
{
q=q->next;
}
q->next=p;
}
}
LNode * GetFirstNode(LNode *head)
{
if(head->next==NULL) return NULL;
else
{
LNode *p;
p=head->next;
head->next=p->next;
return p;
}
}
void AppendNode(LNode *head,LNode *node)
{
if(head==NULL) return;
else
{
LNode *p;
p=head;
while(p->next!=NULL)
{
p=p->next;
}
p->next=node;
node->next=NULL;
}
}
void Total(LNode *L,LNode *head)
{
LNode *p;
p=L;
while(p->next!=NULL)
{
p=p->next;
}
p->next=head->next;
}
int Power(int a,int n)
{
int y;
if(n==0)
return 1;
else
{
y=Power(a,n/2);
y=y*y;
if(n%2==1)
y=y*a;
}
return y;
}
int GetNum(LNode *p,int i)
{
int data=p->data;
int a;
i--;
a=data/Power(10,i);
return a%10;
}
//第二个形参表示参加排序的整数最大位数一共有count位数字
void radix_sort(LNode *head,int count)
{
LNode *p[10],*q;
int i,j,k;
for(j=1;j<=count;j++)
{
//十个头结点初始化
for(i=0;i<10;i++)
{
Initiate(&p);
}
//链表从头到尾扫描，并将扫描到的节点脱离链表。
while(head->next!=NULL)
{
q=GetFirstNode(head);
k=GetNum(q,j); //取得链表节点第j位的元素值k
AppendNode(p[k],q); //将该节点连接到10个链表相应的位置
}
//将10个链表从0-9依次连接到head节点后面
for(i=0;i<10;i++)
{
Total(head,p);
}
}
for(i=0;i<10;i++)
{
delete(p);
}
}
void printSL(LNode *head)
{
LNode *p;
p=head->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
void main()
{
LNode *head;
Initiate(&head);
Insert(head,1113);
Insert(head,4212);
Insert(head,1232);
Insert(head,6533);
Insert(head,2332);
Insert(head,123);
Insert(head,23);
radix_sort(head,4); //表示参加排序的整数最大位数一共有4位数字
printSL(head);
system("pause");
}

只看该作者 · 2017-1-5 12:34

附上使用双向链表实现的代码：

[cpp] view plain copy

#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=(SLnode *)malloc(sizeof(SLnode));
assert(Lhead!=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);
}
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");
}

只看该作者 · 2017-1-6 21:04

这个链表排序的方式很新颖的，，不知道效率的怎样？

【转】基数排序(链表运用)

相关帖子