基数排序算法思想

n个记录的关键字进行排序，每个关键字看成是一个d元组：ki=(ki1, ki2,..., kid)，其中c0 <=kij <=cr-1 ( 1 <=i <=n, 1 <=j <=d )。

排序时先按kid 的值，从小到大将记录分到r（称为基数）个盒子中，再依次收集；然后按kid-1的值再这样作。直至按ki1分配和收集序列为止，排序结束。

在关键字为数字时，r=10, 0 <=ci <=9， 1 <=i <=d；

在关键字为字母时 r=26, ’A’ <=ci <=’Z’, 1 <=i <=d。

例子一组数：12、 104、 13、 7、 9

*（1）按个位数排序是12、13、104、7、9

*（2）再根据十位排序104、7、9、12、13

*（3）再根据百位排序7、9、12、13、104

如果在某一位的数字相同，那么排序结果要根据上一轮的数组确定，举个例子来说：07和09在十分位都是0，但是上一轮排序的时候09是排在07后面的；同样举一个例子，12和13在十分位都是1，但是由于上一轮12是排在13前面，所以在十分位排序的时候，12也要排在13前面。

基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。