radixsort.cpp

包含8种常用的排序。如快速排序

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <string.h>
#include <math.h>
//#include <algorithm>
//using namespace std;
#define MAX 10000
int r[MAX];
#define RADIX 10
#define D 5


typedef struct node //定义每一个数为一个结点
{
	int key[5];    //该数字为五位数字
	int next;
}NODE;

void convert(int num,int converted[])//将每个数字的每个数位（从高位到低位）存储在key[0]～key[5]中
{
	int i,temp;
	temp=num;
	for(i=0;i<D;i++)
	{
		converted[i]=temp/(int(pow(10,D-i-1)));
		
          temp=temp-converted[i]*(int(pow(10,D-i-1)));
		
	}
}

void RadixSort(NODE r[],int d,int radix,int n)  //基数排序
{   
	int h[RADIX],t[RADIX];
	int p,i,j,k;


	for(i=1;i<n;i++) r[i].next=i+1; //将n个数字用指针连成一个链
	r[n].next=0; r[0].next=1;

	for(j=d-1;j>=0;j--) //用j控制排序的次数（有几位数字就需要几次排序）
	{   
		for(i=0;i<radix;i++) { h[i]=t[i]=0; }
		p=r[0].next;
		while(p)
		{
			i=r[p].key[j];
			if(h[i]) 
			{ r[t[i]].next=p;
			  t[i]=p;
			  p=r[p].next;
			}
			else
			{
				h[i]=t[i]=p;
				p=r[p].next;
			}
		}
		i=0;
		while(!h[i]) ++i;
		r[0].next=h[i];k=i+1;
		while(k<radix)
		{
			if(h[k]) { r[t[i]].next=h[k];i=k;}
			k++;
		}
		r[t[i]].next=0;
	}

}

void main()
{
	clock_t start=clock();/*程序开始运行的时间*/
	int i,j,num ;
	NODE List[MAX];

	
	printf("Please input the number of the numbers: ");
	scanf("%d",&num);
	
    //srand((unsigned int)time(NULL));//随时间的不同产生不同的随机数
	for(i=0;i<num;i++)
	{
		r[i]=rand()%num+1;
	}
	printf("The %d nums is produced automatically:\n",num);
    for(i=0;i<num;i++)
	{ printf("%10d",r[i]); }

    
	for(i=0;i<num;i++)
	{
		convert(r[i],List[i+1].key );//将每个数字的每个数位（从高位到低位）存储在key[0]～key[4]中
	}

	RadixSort(List,D,RADIX,num); //基数排序
	i=List[0].next;
	//getch();

	printf("\nAfter sorting:\n");
	while(i)
	{   for(j=0;j<D;j++) printf("%d",List[i].key[j] ); //一个for循环只输出一个五位数字
	    printf("->");
		i=List[i].next;//当i=List[num].next=0时,while循环结束
	}

	clock_t end=clock(); /*程序结束运行的时间*/
    cout<<"\n"<<"整个程序运行的时间为:";
    cout<<(end-start)<<"毫秒\n";	
}