[演算法] 基數排序法
基數排序法，是按照位數順序進行排序的一種方法，從個位數開始排序至最大位數稱為LSD(Least sgnificant
digital)，從最大位數排序至個位數稱為MSD(Most sgnificant digital)，利用這種分配性的排列方式，稱為基數排序法(Radix
Sort)。
例：
２ １２ ８ ７ ３９ １
插入排序(LSD)：
[第一次]
０２ １２ ０８ ０７ ３９ ０１ (
取得個位數，並進行個位數排序 )
１ ２ １２ ８ ９ ３９（結果）
[第二次]
０１ ０２ １２ ０８ ０９ ３９ (
利用個位數排序結果，取得個十數，並進行十位數排序 ，如數不足十位數則為０)
１ ２ ８ ９ １２ ３９（結果）
實作時，需要用到較多的Buffer來暫時儲存結果。
程式範例（ Linux C ）：
|
#include
#include
#include
#include
#include
/*************************************************************************/
/*! \struct Leo_Radix
* \brief Leo_Radix function,IN: None,OUT: None
* \details Leo_Radix function \n
* \author Leo Cheng
*/
/*************************************************************************/
int
Leo_Radix(int *Data,int Input_Number)
{
int
RadixData[Input_Number];
int
RadixNumberBuffer[Input_Number];
int
RadixDataBuffer[Input_Number];
int
RadixDataBuffer1[Input_Number];
int
i=0,j=0,k=0;
/*Start in LSD（Least sgnificant digital）*/
/*Reset with one place*/
k=0;
//Get one place from Data to RadixNumberBuffer
for(i=0;i
{
RadixNumberBuffer[i] = Data[i] - (Data[i]/10)*10;
}
//Get one place in RadixNumberBuffer
for(i=0;i<=9;i++)
{
for(j=0;j
{
if(RadixNumberBuffer[j]
== i)
{
RadixDataBuffer[k] = *(Data+j);
k = k + 1;
}
}
}
k=0;
/*Reset with tens place*/
//Get tens place from RadixDataBuffer to RadixNumberBuffer
for(i=0;i
{
if(RadixDataBuffer[i]
< 10)
{
RadixNumberBuffer[i] = 0;
}
else
{
RadixNumberBuffer[i] = RadixDataBuffer[i]/10;
}
}
//Get tens place in RadixNumberBuffer
for(i=0;i<=9;i++)
{
for(j=0;j
{
if(RadixNumberBuffer[j]
== i)
{
RadixDataBuffer1[k] = RadixDataBuffer[j];
k = k + 1;
}
}
}
//---Show InputData---//
for(i=0;i
{
printf(" %d",*(Data+i));
}
printf("\n");
//---Show Answer---//
for(i=0;i
{
printf(" %d",RadixDataBuffer1[i]);
}
printf("\n");
return 0;
}
/*************************************************************************/
/*! \struct main
* \brief main function,IN: None,OUT: None
* \details main function \n
* \author Leo Cheng
*/
/*************************************************************************/
void main()
{
int Input_Number = 10;
int
InputData[Input_Number];
int i;
srand(time(NULL));
for( i=0 ; i <
Input_Number ; i++ )
{
InputData[i]=(rand()%100)+1;
}
Leo_Radix(InputData,Input_Number);
} |
哪來的９...