利用递归算法实现的基数排序算法

#include <iostream> #include <iomanip> #include <cstdlib> #include <conio.h> #include <math.h> using namespace std; int gl[4][8];//记录每次排序的结果，为了显示过程结果 int* RadixSort(int *P,int n); //递归函数 int* Sort(int *Y,int m);//对相应位上的数归类，放入空表，然后将表按顺序连接 int decode(int,int);//分解成相应的个，十，百，千位上的数字 int *RadixSort(int *P,int n) { int *L; if(n == 0) { L=Sort(P,0); return L; } L=RadixSort(P,n-1); L=Sort(L,n); return L; } int decode(int m,int z) //分解成相应的个，十，百，千位上的数字 { int d; switch(m) { case 0:d=z%10;break; case 1:d=z/10;d=d%10;break; case 2:d=z/100;d=d%10;break; case 3:d=z/1000;d=d%10;break; } return d; } int* Sort(int *r,int m) { int k=0; int LL[10][10]={0};//10个空表 int count[10]={0};//记录LL每个表中的的非零元素个数 int d; int *lr=NULL; lr=r; for(int j=0;j < 8;j++) { int a=1000; d=decode(m,r[j]);//获得相应的（m）位上的数字 switch(d) //把（m）位上的数字归类，并把相应的r[j]放入对应的表中 { case 0:LL[0][count[0]]=r[j];count[0]++;break; case 1:LL[1][count[1]]=r[j];count[1]++;break; case 2:LL[2][count[2]]=r[j];count[2]++;break; case 3:LL[3][count[3]]=r[j];count[3]++;break; case 4:LL[4][count[4]]=r[j];count[4]++;break; case 5:LL[5][count[5]]=r[j];count[5]++;break; case 6:LL[6][count[6]]=r[j];count[6]++;break; case 7:LL[7][count[7]]=r[j];count[7]++;break; case 8:LL[8][count[8]]=r[j];count[8]++;break; case 9:LL[9][count[9]]=r[j];count[9]++;break; } } for(int x=0;x<10;x++) {//把LL表中的元素按顺序放入lr if(count[x] >= 1) { for (int w=0;w<count[x];w++) { lr[k]=LL[x][w]; k++; } } } for(int t=0;t<8;t++) gl[m][t]=lr[t]; return lr; } void main() { cout<<" "<<"<--------------------------->"<<'\n'; cout<<" "<<"| |"<<'\n'; cout<<" "<<"| 基数排序 |"<<'\n'; cout<<" "<<"| |"<<'\n'; cout<<" "<<"<--------------------------->"<<'\n'; int *List; int L[8]={7467,1247,3275,4692,9187,9134,4675,1239}; int Lr[8]={7467,1247,3275,4692,9187,9134,4675,1239}; int* RadixSort(int *P,int n);//函数声明 int* Sort(int *Y,int m);//函数声明 int decode(int,int);//函数声明 List=RadixSort(L,3);//调用递归函数 cout<<'\n'<<"初始数列"<<" 第1位数排列"<<" 第2位数排列"<<" 第3位数排列"<<" 第4位数排列"<<'\n'; for(int t=0;t<8;t++) cout<<" "<<Lr[t]<<" "<<gl[0][t]<<" "<<gl[1][t]<<" "<<gl[2][t]<<" "<<gl[3][t]<<'\n'; cout<<"---------------------------------------------------------------------Done!"; getch(); }