LSD是比較好的。
#include<stdio.h>
#define Max_ 10 //數組個數
#define RADIX_10 10 //整形排序
#define KEYNUM_31 10 //關鍵字個數，這里為整形位數
// 打印結果
void Show(int arr[], int n)
{
int i;
for ( i=0; i<n; i++ )
printf("%d ", arr[i]);
printf("\n");
}
// 找到num的從低到高的第pos位的數據
int GetNumInPos(int num,int pos)
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
temp *= 10;
return (num / temp) % 10;
}
//基數排序 pDataArray 無序數組；iDataNum為無序數據個數
void RadixSort(int* pDataArray, int iDataNum)
{
int *radixArrays[RADIX_10]; //分別為0~9的序列空間
for (int i = 0; i < 10; i++)
{
radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
radixArrays[i][0] = 0; //index為0處記錄這組數據的個數
}
for (int pos = 1; pos <= KEYNUM_31; pos++) //從個位開始到31位
{
for (int i = 0; i < iDataNum; i++) //分配過程
{
int num = GetNumInPos(pDataArray[i], pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = pDataArray[i];
}
for (int i = 0, j =0; i < RADIX_10; i++) //收集
{
for (int k = 1; k <= radixArrays[i][0]; k++)
pDataArray[j++] = radixArrays[i][k];
radixArrays[i][0] = 0; //復位
}
}
}
int main()
{ //測試數據
int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
//排序前數組序列
Show( arr_test, Max_ );
RadixSort( arr_test, Max_);
//排序后數組序列
Show( arr_test, Max_ );
return 0;
}
|
