基数排序（radix sorting）将所有待比较数值(正整数)统一为同样的数位长度，数位较短的数前面补零。 然后 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后， 数列就变成一个有序序列。
假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b为次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。
基数排序的简单描述就是将数字拆分为个位十位百位，每个位依次排序。因为这对算法稳定要求高。因为基数排序要经过d (数据长度)次排序， 每次使用计数排序， 计数排序的复杂度为 O(n), d 相当于常量和N无关，所以基数排序也是 O(n)。基数排序虽然是线性复杂度， 即对n个数字处理了n次，但是每一次代价都比较高， 而且使用计数排序的基数排序不能进行原地排序，需要更多的内存， 并且快速排序可能更好地利用硬件的缓存， 所以比较起来，像快速排序这些原地排序算法更可取。对于一个位数有限的十进制数，我们可以把它看作一个多元组，从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。
代码如下：
基数排序 - 太阳落雨 - 博客频道 - CSDN.NET http://blog.csdn.net/cjf_iceking/article/details/7943609
Void RadixSort(Node L[],length,maxradix) { int m=1,n=0,k=0,lsp=0; k=1;m=1; int temp[10][length-1]; for(int i=0;i<10;i++) for(int j=0;j<length;j++) temp[i][j]=-1; //清空临时空间 while(k<maxradix) //遍历所有关键字 { for(int i=0;i<length;i++) //分配过程 { if(L[i]<m) Temp[0][n]=L[i]; else lsp=(L[i]/m)%10; //确定关键字 temp[lsp][n]=L[i]; n++; } n=0; for(int i=0;i<10;i++) for(int j=0;j<length;j++) if(temp[i][j]!=-1) L[n++]=temp[i][j]; //收集 n=0; m=m*10; k++; } }