sort_radix.cpp

自己编写的排序算法的代码

#include <fstream.h>
#include "data.h"

//k为待排的位，此函数的返回值是待排整数的第k位
int digit_sort(int *a,int s,int k)
{
	int i,temp;
	temp=a[s];
	for(i=0;i<k-1;i++)
	    temp=temp/10;
	temp=temp%10;
	return temp;
}

//做为基数排序的子排序的计数排序
void Count_Radix(int *a,int *b,int k)
{                    
	int i,temp[10];
	for(i=0;i<10;i++)                     
		temp[i]=0;
    for(i=0;i<number;i++)                     
	    temp[digit_sort(a,i,k)]=temp[digit_sort(a,i,k)]+1;
    for(i=1;i<10;i++)                     
	    temp[i]=temp[i]+temp[i-1];
    for(i=number-1;i>=0;i--)
	{
		b[temp[digit_sort(a,i,k)]-1]=a[i];
		temp[digit_sort(a,i,k)]=temp[digit_sort(a,i,k)]-1;
	}
}

//基数排序
void Radix_sort(int a[])
{
	int i,j,d,*Tarray;
	Tarray=new int[number];
	if(!Tarray)
	{
		cout<<"内存空间申请失败"<<endl;
		return;
	}
	d=digit();
	for(i=0;i<number;i++)
		Tarray[i]=a[i];
	j=0;
	for(i=0;i<d;i++)
	{  
        if(j%2)
            Count_Radix(Tarray,a,i+1);
		else
			Count_Radix(a,Tarray,i+1);
		j++;
	}
	if(j%2)
	{
		for(i=0;i<number;i++)
			a[i]=Tarray[i];
	}
	delete Tarray;
}