radixsort.cpp

这是一段关于四种排序方法的完全源代码及其相互之间的比较,包括:Heap sort,Merge sort,Quick sort,Radix sort

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

typedef struct Lnode
{
	int data;
	struct Lnode *next;
}Inode,*Linklist;

int findj(int a,int j);//返回a的第j位数字,a的长度小于k
void radixsort(Inode *L,int k);
Inode *gettail(Inode *L);
void ShowList(Inode *head);
void InitList(Inode *&L);



void main()
{
	int n;
	cout<<"请输入n:";
	cin>>n;
	srand(time(0));
	Inode *L,*s,*p,*head;
	s=new Inode;
	s->data=n;
	head=NULL;
	for(int i=1;i<=n;i++)
	{
		if(head==NULL)
		{
			head=s;
		}
		else
		{
			p->next=s;
		}
		p=s;
		s=new Inode;
		s->data=rand();
	}
	p->next=NULL;
	delete s;
	InitList(L);
	L->next=head;
	cout<<"生成随机数组为:"<<'\n';
	ShowList(L);
	radixsort(L,5);
	cout<<"基数排序后数组为:"<<'\n';
	ShowList(L);

}

//初使化表
void InitList(Inode *&L)
{
	L=new Inode;
	L->next=NULL;
}

void ShowList(Inode *head)
{
	head=head->next;
	while(head)
	{
		cout<<head->data<<'\t';
		head=head->next;
	}
	cout<<endl;
}
Inode *gettail(Inode *L)
{
	Inode *p,*q;
	p=L;
	while(p)
	{
		q=p;
		p=p->next;
	}
	return q;
}
int findj(int a,int j)
{
	 return ((int)(a/pow(10,j-1)))%10;
}


void radixsort(Inode *L,int k)
{
	int i;
	Inode *a;
	Inode *L0,*L1,*L2,*L3,*L4,*L5,*L6,*L7,*L8,*L9;
	Inode *p0,*p1,*p2,*p3,*p4,*p5,*p6,*p7,*p8,*p9;
	Inode *L0_tail,*L1_tail,*L2_tail,*L3_tail,*L4_tail,*L5_tail,*L6_tail,*L7_tail,*L8_tail;
	for(int j=1;j<=k;j++)
	{
		InitList(L0);p0=L0;
		InitList(L1);p1=L1;
		InitList(L2);p2=L2;
		InitList(L3);p3=L3;
		InitList(L4);p4=L4;
		InitList(L5);p5=L5;
		InitList(L6);p6=L6;
		InitList(L7);p7=L7;
		InitList(L8);p8=L8;
		InitList(L9);p9=L9;
		while(L->next)
		{
			a=L->next;
			L->next=a->next;
			a->next=NULL;
			i=findj(a->data,j);
			switch(i)
			{
			case 0:p0->next=a;p0=a;break;
			case 1:p1->next=a;p1=a;break;
			case 2:p2->next=a;p2=a;break;
			case 3:p3->next=a;p3=a;break;
			case 4:p4->next=a;p4=a;break;
			case 5:p5->next=a;p5=a;break;
			case 6:p6->next=a;p6=a;break;
			case 7:p7->next=a;p7=a;break;
			case 8:p8->next=a;p8=a;break;
			case 9:p9->next=a;p9=a;break;
			default:return;
			}
		}
		L0_tail=gettail(L0);
		L1_tail=gettail(L1);
		L2_tail=gettail(L2);
		L3_tail=gettail(L3);
		L4_tail=gettail(L4);
		L5_tail=gettail(L5);
		L6_tail=gettail(L6);
		L7_tail=gettail(L7);
		L8_tail=gettail(L8);
		L8_tail->next=L9->next;
		L7_tail->next=L8->next;
		L6_tail->next=L7->next;
		L5_tail->next=L6->next;
		L4_tail->next=L5->next;
		L3_tail->next=L4->next;
		L2_tail->next=L3->next;
		L1_tail->next=L2->next;
		L0_tail->next=L1->next;
		L->next=L0->next;
	}
}