一、原理
基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,K为数组的数的最大的位数
基数排序是按照低位先排序,然后收集:在按照高位排序,然后在收集,以此类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序。分别收集,所有是稳定的
(1)取得数组中的最大数,并取得位数
(2)array为原始数组,从最低位开始取每个位组称radix数组
(3)对radix进行计数排序
最佳情况:T(n) = O(n * k) 最差情况: T(n) = O(n * k) 平均情况: T(n) = O(n * k)
二、代码实现