10.基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或“箱排序”（bin sort）。它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。基数排序法是属于稳定性的排序，受数据状况的影响较大，在某些时候，基数排序法的效率高于其它的稳定性排序法。

基数排序是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

时间复杂度 ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。
即时间复杂度：N+K；（N+K）*d， d为位数，K为范围（0-9）
空间效率：
即空间复杂度：N+K