一、简介
基数排序（Radix Sort）属于“分配式排序”（Distribution Sort）。基数排序法是属于稳定性的排序。设待排序列为n个记录，d个关键码，关键码的取值范围为Radix，则进行基数排序的时间复杂度为O(d(n+Radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(Radix)，共进行d趟分配和收集。
二、算法基本思想
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
LSD的算法思路如下：
将所有待比较数值（这里以正整数为例）统一为同样的数位长度，数位较短的数前面补零。设一整数的十进制位数表示为k1,k2...kd，其中k1为高位，kd为低位。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。即先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
MSD的算法思路如下：
MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个组中建立“子组”，将每个桶子中的数值按照下一数位的值分配到“子组”中。在进行完最低位数的分配后再合并回单一的数组中。即先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。所以，MSD方法用递归的思想实现最为直接。
三、算法实现（C++模板）
LSD的实现如下：
template <typename T>
int _RadixSort_GetNumInPos(T nData,const int pos)//获取特定位上的数
{
unsigned int* pData = (unsigned int*)&nData;
int nTemp = 1;
for(int i = 0;i < (pos - 1);i++)
{
nTemp *= 10;
}
return ((*pData) / nTemp) % 10;
}
template <typename T>
bool CountingSortWithRadixArray(T* pFirst,T* pLast,int* pRadixFirst,const int nMaxValue)//计数排序模板
{
bool bIsReverse = false; //判断输入数组指针是否逆序
T* pTemp = NULL;
if((pFirst == NULL) || (pLast == NULL)) //判断输入参数的正确性
{
cout<<"Input parameters error!"<<endl;
return false;
}
if(pFirst > pLast) //若输入数组指针逆序，则首尾指针交换
{
bIsReverse = true;
pTemp = pFirst;
pFirst = pLast;
pLast = pTemp;
}
const int nLength = pLast - pFirst + 1; //计算输入数据长度
int* pCountArray = new int[nMaxValue]; //对数据值进行计数，根据最大数据值进行数组申请
T* pTempArray = new T[nLength]; //辅助数组
pTemp = pRadixFirst;
for(int i=0;i<nMaxValue;i++)
{
pCountArray[i] = 0; //计数器清零
}
for(int i=0;i<nLength;i++) //对数据计数
{
pCountArray[*pTemp] = pCountArray[*pTemp] + 1;
++pTemp;
}
for(int i=1;i<nMaxValue;i++) //统计特定数据前的数据数目
{
pCountArray[i] = pCountArray[i] + pCountArray[i-1];
}
for(int i=nLength-1;i>=0;i--) //对数据进行重新排列
{
pTempArray[pCountArray[pRadixFirst[i]]-1] = pFirst[i];
--pCountArray[pRadixFirst[i]];
}
for(int i=0;i<nLength;i++) //将重新排列的数据重新赋值给原数组
{
pFirst[i] = pTempArray[i];
}
if(bIsReverse) //若输入数组倒序，则重新进行逆序
{
while(pFirst < pLast)
{
Swap(*pFirst,*pLast);
++pFirst;
--pLast;
}
}
delete []pCountArray;
delete []pTempArray;
return true;
}
template <typename T>
bool RadixSortLSD(T* pFirst,T* pLast) //基于计数排序的LSD实现模板
{
bool bIsReverse = false; //同上
T* pTemp = NULL;
if((pFirst == NULL) || (pLast == NULL)) //同上
{
cout<<"Input parameters error!"<<endl;
return false;
}
if(pFirst > pLast)
{
bIsReverse = true;
pTemp = pFirst;
pFirst = pLast;
pLast = pTemp;
}
int nLength = pLast - pFirst + 1; //计算数组长度
int* pRadixArray = new T[nLength]; //记录每位数据
T* pTempArray = new T[nLength]; //辅助数组
pTemp = pFirst;
bool bIsOK = false; //判断是否已经到达最高位
for(int i=0;i<nLength;i++)
{
pRadixArray[i] = 0;
}
int nPos = 1;
while(!bIsOK)
{
bIsOK = true;
for(int i=0;i<nLength;i++)
{
int nPosNum = _RadixSort_GetNumInPos(pTemp[i],nPos);//获取特定位数值
pRadixArray[i] = nPosNum;
if(pRadixArray[i] > 0)
bIsOK = false;
}
++nPos;
if(bIsOK) //若已对排序完最高位，则退出循环
break;
CountingSortWithRadixArray(pFirst,pLast,pRadixArray,RADIX_NUM);//这里采用稳定的计数排序按数组中每位数字进行排序
}
if(bIsReverse) //逆序数组
{
while(pFirst < pLast)
{
Swap(*pFirst,*pLast);
++pFirst;
--pLast;
}
}
delete []pRadixArray;
delete []pTempArray;
return true;
}
MSD的实现如下：
template <typename T>
bool RadixSortMSD(T* pFirst,T* pLast,const int nPos) //MSD实现模板
{
bool bIsReverse = false;
T* pTemp = NULL;
if((pFirst == NULL) || (pLast == NULL))
{
cout<<"Input parameters error!"<<endl;
return false;
}
if(pFirst > pLast)
{
bIsReverse = true;
pTemp = pFirst;
pFirst = pLast;
pLast = pTemp;
}
int nLength = pLast - pFirst + 1;
T* pBucket = new T[nLength];
int* pCount = new int[RADIX_NUM];
for(int i=0;i<RADIX_NUM;i++)
{
pCount[i] = 0;
}
for(pTemp=pFirst;pTemp<=pLast;pTemp++) //稳定计数排序
{
pCount[_RadixSort_GetNumInPos(*pTemp,nPos)]++;
}
for(int i=1;i<RADIX_NUM;i++)
{
pCount[i] = pCount[i] + pCount[i-1];
}
for(pTemp = pLast;pTemp>=pFirst;pTemp--)
{
int j = _RadixSort_GetNumInPos(*pTemp,nPos);
pBucket[pCount[j]-1] = *pTemp;
--pCount[j];
}
for(int i=0;i<nLength;i++) //将数组放入子数组中
{
pFirst[i] = pBucket[i];
}
delete []pBucket;
for(int i=0;i<RADIX_NUM;i++)
{
int nLeft = pCount[i];
int nRight = pCount[i+1] - 1;
if(nLeft < nRight && nPos > 1)
{
RadixSortMSD(pFirst+nLeft,pFirst+nRight,nPos-1); //对子数组递归进行MSD排序
}
}
delete []pCount;
if(bIsReverse)
{
while(pFirst < pLast)
{
Swap(*pFirst,*pLast);
++pFirst;
--pLast;
}
}
return true;
}
基数排序没有利用比较进行排序，而是对数据进行了另一个纬度的分解，分解后在利用复杂度为O（n）的桶排序或计数排序对分解后的数据进行排序，这样得到了更好的时间复杂度。但基数排序是否比基于比较的排序算法更好呢？然而，在实际应用中，基数排序时间复杂度O（n）中的常数因子会有所不同，对于要处理的n个关键字，尽管基数排序执行的遍数可能比快速排序要少，但每一遍所需的时间可能要长的多。哪个排序算法更好取决于底层机器的实现特性（例如，快速排序通常可以比基数排序更为有效地利用硬件缓存），同时还取决于特定输入的数据。此外，利用计数排序作为中间稳定排序的基数排序不是原地排序，而很多O（nlogn）的比较排序算法则可以做到原地排序。因此，当内存容量比较宝贵时，像快排这样的原地排序算法可能更为可取一些。
（做个宣传，哈哈，要想了解更多基本数据结构及算法实现详见我的GitHub，我会尽快更新！！）
GitHub地址是：https://github.com/daiyl0320/IntroductionToAlgorithms