基数排序基于多关键字排序的思想，即把一个逻辑关键字拆分成多个关键字。
基数排序有两种实现方式：
- 第一种叫做最高位优先（MSD），即先按最高位排成若干子序列，再对每个子序列按次高位排。
- 第二种叫做最低位优先（LSD），这种方式不必分成子序列，每次排序全体元素都参与。最低位可以优先这样进行，不通过比较，而是通过“分配”和“收集”。
由于不需要分堆并对每堆单独排序，LSD方法往往比MSD简单而开销小。
基数排序适合的场景是序列中的元素很多，但组成元素的关键字的取值范围较小。如果关键字的取值范围也很大，如26个字母，且序列中大多数元素的最高位关键字都不相同，那么这时可以考虑使用“最高位优先法”，先根据最高位排成若干个子序列，然后分别对这些子序列进行直接插入排序。
感觉桶排序与基数排序貌似是一样的。【待解决】
算法代码为：
写了好久，归根结底还是链表、指针的不熟悉造成的，加油！
#include "stdafx.h"
#include <iostream>
using namespace std;
//链表使用功底有待加强！！
struct Node
{
int value;
Node *next;
};
int getDigit(int num, int loc)
{//取数字num第loc位上的数字
for(int i=0; i < loc; i++)//i从0开始
num /= 10;
return num%10;
}
int maxBits(int data[], int size)
{//数组中数字的最大位数;相当于进行几趟分配
int max = 0, temp, current;
for(int i=0; i<size; i++)
{
temp = 0;
current = data[i];
while(current)
{
temp++;
current /= 10;
}
if(temp > max)
max = temp;
}
return max;
}
void RadixSort(int data[], int size)
{//其实应该还可以有个表示基数的参数，现在默认为10
if(data == NULL || size <= 0)
return;
int rankNum = maxBits(data, size);
Node Bucket[10];//建立10个桶
if(Bucket == NULL)
return ;
int i,idNum;
Node *p,*q;//插入节点时所用的临时变量
for(int rank = 0; rank < rankNum; rank++)
{//进行rankNum趟排序
for(int i = 0; i < 10; i++)
{//初始化桶
Bucket[i].value = -1;
Bucket[i].next = NULL;
}
for(int i = 0; i < size; i++)
{//依次如桶
Node *pNew = new Node();//()表示值初始化
pNew->value = data[i];
pNew->next = NULL;
idNum = getDigit(data[i],rank);
if(Bucket[idNum].next == NULL)
Bucket[idNum].next = pNew;
else
{
p = &Bucket[idNum];//注意&
while(p->next != NULL)
p = p->next;
p->next = pNew;
}
}
int j=0;//初始化
for(i=0; i < 10; i++)
{//依次遍历10个桶
p = Bucket[i].next;
if(p == NULL)
continue;
while(p != NULL)
{
data[j++] = p->value;
q = p;
p = p->next;
delete q;//勿忘释放空间！！
}
}
for(int i=0;i<size;++i)
cout<<data[i]<<" ";
cout<<endl;
}
}
int main()
{
int unsorted[] = {3,36,1,4,15,5,8,14,9,9,10};
int length = sizeof(unsorted)/sizeof(int);
for(int i=0;i<length;++i)
cout<<unsorted[i]<<" ";
cout<<endl;
RadixSort(unsorted,length);
for(int i=0;i<length;++i)
cout<<unsorted[i]<<" ";
cout<<endl;
return 0;
}
写在最后：其实，这些经典的算法的思想，都是非常熟悉的，但，知道容易动手难，尤其是最后这个基数排序卡了很久，还是多动手吧，无他，唯手熟尔！