首页 > 代码库 > 基数排序的总结

基数排序的总结

1.基数排序不是基于比较的排序,是一种线性排序。

2基数排序如何实现?

列入:

3, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
 
总结: 算法的总步数为,数组中的最高位数为k,则时间复杂度为kn,空间复杂度为O(n);
3.基数排序一定是稳定的
例如  278 874, 首先按低位为 174 278 ,如果按照7来看的话,这次如果7相等,则顺序不。

基数排序的总结