基数排序

基数排序

基数排序并不是基于「选择」和「移动」来进行的。基数排序是一种「多关键字排序」。

基数排序的思想：先对次关键字排序，然后使用「稳定的」排序方法对主关键字排序，最后得到的序列是总体有序的。

其中一种实现为：根据「基数」将元素加入到不同的队列/桶里，不断重复「分配-收集」的操作。

空间复杂度：， 是基数的大小，需要开辟这么多个队列
时间复杂度：，其中 表示数字的位数。每次分配需要 ，每次收集需要 ，一共需要进行 趟排序
基数排序是稳定的。（每一趟排序都是稳定的）