基数排序（Radix Sort）：是一种非比较型的整数排序算法 。
基数排序的基本原理是，按照整数的每个位数分组 。在分组过程中，对于不足位的数据用0补位 。
基数排序按照对位数分组的顺序的不同，可以分为LSD基数排序和MSD基数排序 。
LSD基数排序，是按照从低位到高位的顺序进行分组排序 。例如：1,2,3,4,5,6,7,8,9,10第一次分组后为 10,1,2,3,4,5,6,7,8,9 。
【排序方法的时间复杂度 稳定排序算法有哪些】MSD基数排序，是按照从高位到低位的顺序进行分组排序 。例如：1,2,3,4,5,6,7,8,9,10 第一次分组以后为 1,10,2,3,4,5,6,7,8,9 。
上述两种方式不仅仅是对位数分组顺序不同，其实现原理也是不同的 。这里我们只先介绍LSD基数排序 。
首先我们看LSD基数排序是如何进行的
对于序列中的每个整数的每一位都可以看成是一个桶，而该位上的数字就可以认为是这个桶的键值 。这句话应该怎么理解呢，我们来看这样的一个序列
170, 45, 75, 90, 802, 2, 24, 66
这是一个整数序列，我们知道，对于每个整数的每一位上的值肯定是介于0和9之间的 。因此，要想对这个序列进行LSD排序，那就必须有10个桶 。这10个桶的索引分别就是0——9这十个数 。对于LSD基数排序来说，每一次分组过程就是将相应的整数放进相应的桶中 。
拿第一次分组来说吧，对于每个整数要按照个位上的数进行分组 。那么我们看170，其个位为0，所以说170应该放进0这个桶中 。然后以此类推 45放在5这个桶中 。
所以上述序列的第一次分组后，各个整数所在的桶如下
0: 170, 090
1: 空
2: 802, 002
3: 空
4: 024
5: 045, 075
6: 066
7–9: 空
然后再将这些数依次收集起来，第一次分组再组合以后的序列为
170, 90, 802, 2, 24, 45, 75, 66
接着就是针对十位上的数进行分组入桶，入桶的情况如下
0: 802, 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 170, 075
8: 空
9: 090
再次整理起来以后为下面的序列
802, 2, 24, 45, 66, 170, 75, 90
最后再次进行第三次（百位上的数）分组入桶
0: 002, 024, 045, 066, 075, 090
1: 170
2–7: 空
8: 802
9: 空
整理起来以后，我们发现整个序列已经是有序的了
2, 24, 45, 66, 75, 90, 170, 802
整个LSD基数排序的过程就是这样的，当然不同的程序可以构造不同的存放数据的桶的形式 。但是其原理是相同的 。
LSD基数排序是一个快速的稳定排序算法 。其时间复杂度可以表示为O(Kn) 。其中n就是待排序序列的元素个数，K是数字的位数 。对于这个K我们应该怎样理解这个需要为大家说明一下 。有时候K可以看做是一个常数——对于上述例子，其中K就是3 。因为在上面的例子中最大的数是802，该数有3位 。因此，在这种情况下，基数排序要比任何比较型的排序算法的效率要高 。因为在比较型的排序算法中，最优的排序算法的时间复杂度也是O（nlogn） 。
推荐阅读
- 山药出芽还能吃吗 吃了出芽的山药会怎么样
- 反弓水为何也叫发财水 反弓水也叫发财水的原因
- 挑多音字组词 多音字挑的组词
- 山莓和树莓的区别 山莓和树莓区别有哪些
- 未来最好的投资项目 现在投资什么最赚钱
- 在家有什么赚钱的可以做，分享四种坐在家里赚钱的方法
- 麻酱拌面的家常做法 麻酱拌面怎么做
- 男生拍一拍文字文案 适合男生拍一拍文字文案
- 有关于唯美的爱情文案 优美的爱情文案介绍
- 牛顿三定律 牛顿三定律的解释