目錄

一、算法思路

二、C#語言實現

三、C語言實現

---

一、算法思路

1. 思想基礎

基數排序的思想就是先找出待排序中的最大者，然后按最大者申請一個足夠大的內存空間，并將其初始化為零，然后將所有待排序的數裝入其中，標記裝入的數，最后按下標依次返回所有數即可。

2. 函數

public void RadixSort(int []A,int n)

??????????? {

??????????????? int Max,i,j,m,nz;

??????????????? Max=A[0];

??????????????? for (i=0;i<n;i++)//獲得待排序列中的最大值

??? ??????????? {

??? ??????????????? if (A[i]>Max)

?????? ??????????? Max=A[i];

??? ??????????? }

??????????? Max++;

//以這個最大樹為桶申請內存，裝入所有數

??????????? int[] pt = new int[Max];

??????????? for(i=0;i<Max;i++)//將數組中的所有數初始化為零

??? ??????????? pt[i]=0;

??????????? for(i=0;i<n;i++)//把這些數據逐個放入這些桶里

??? ??????? {

??? ??????????? m=A[i];

??? ??????????? pt[m]++;//讓裝入的數去做數組的下標

??? ??????? }

??????????? m=0; //回收數據，m是排序結果的下標值

??????????? for(i=0;i<Max;i++)

??? ??????? {

??? ??????????? nz=pt[i];

??????????? ? ?for(j=0;j<nz;j++)

?????? ??????? ????A[m++]=i;

??? ??????? }

??????? }

二、C#語言實現

private void button1_Click(object sender, EventArgs e)
{int i;int []a={278,109,63,83,930,589,184,505,269,8,83};//待排序數RadixSort(a,11);listBox1.Items.Clear();for (i = 0; i < 10; i++)listBox1.Items.Add(a[i].ToString());
}
private void button2_Click(object sender, EventArgs e)
{this.Close();
}

運行情況（完整程序見工程“基數排序”）：

從上面可以看出，基數排序的思想和過程都比較簡單，但效率不是很高。通過該程序，使得對計算機內存有了更深層次的理解；對于基數排序方法，要注意三點：1 構造桶；2 把數據放進桶里； 3 回收數據。

三、C語言實現

#include<stdlib.h>
#include<stdio.h>
#include<windows.h>
void RadixSort(int A[],int n)
{
int Max,i,j,m,nz;
int *pt;
Max=A[0];
for (i=0;i<n;i++){if (A[i]>Max) Max=A[i];}
Max++;
pt=(int *)malloc(Max*sizeof(int));
if (!pt) return;for(i=0;i<Max;i++)pt[i]=0;for(i=0;i<n;i++){m=A[i];pt[m]++;}
m=0;
for(i=0;i<Max;i++){nz=pt[i];for(j=0;j<nz;j++)A[m++]=i;}
free(pt);
}
//獲得n個不重復的隨機數，具體算法不用管
void CreateData(int A[],int n)
{int i,j;srand((unsigned)time(NULL));for(i=0;i<n;i++){A[i]=rand()%n;//以下內容是消除重復，但在數據規模很大的情況下這個過程異常緩慢。/*for(j=0;j<i;j++)while(A[j]==A[i]){A[i]=rand()%n;j=0;}*/}
}void DispTime(SYSTEMTIME sys)
{printf("%4d/%02d/%02d %02d:%02d:%02d.%03d 星期%1d\n" ,sys.wYear,sys.wMonth,sys.wDay ,sys.wHour,sys.wMinute,sys.wSecond,sys.wMilliseconds ,sys.wDayOfWeek); 
}char * DiffTime(SYSTEMTIME systime0,SYSTEMTIME systime1)
{char st[128];sprintf(st,"%4d/%02d/%02d %02d:%02d:%02d.%03d 星期%1d\n",systime0.wYear-systime1.wYear,systime0.wMonth-systime1.wMonth,systime0.wDay-systime1.wDay ,systime0.wHour-systime1.wHour,systime0.wMinute-systime1.wMinute,systime0.wSecond-systime1.wSecond,systime0.wMilliseconds-systime1.wMilliseconds ,systime0.wDayOfWeek-systime1.wDayOfWeek); return st;
}main()
{int i,n=0,m;int *A;SYSTEMTIME sys0,sys1;printf("請輸入要排序的數據個數:");scanf("%d",&m);if(m<0){printf("滾！不解釋~\n");exit(0);}A=(int *)malloc(sizeof(int)*m);if(A==NULL){printf("內存不足、程序退出\n");exit(0);}//獲得隨機數CreateData(A,m);printf("測試數據構造完成\n");GetLocalTime(&sys0); RadixSort(A,m);GetLocalTime(&sys1); //打印數據，在數據規模大的情況下很慢/*n=0;for(i=0;i<m;i++){printf("%d\t",A[i]);n++;if(n==10) {printf("\n");n=0;}}printf("\n");*/DispTime(sys0);DispTime(sys1);printf("用時：%s\n",DiffTime(sys1,sys0));free(A);
}

?