1 基数排序
给定一个序列，对其进行基数排序。基数指的是，数字的个位、十位等等。每一轮的遍历，只关注基数位置的数。
基本思想：不进行关键字的比较，而是依靠“分配”和“收集”。
算法描述：
准备：数字0-9“篮子”。
- 开始：
- 遍历基数（从个位开始）：
- 根据基数位置数的大小，把其放到相应的篮子；
- 按照0-9的顺序对篮子里的数进行收集；
- 遍历基数（从个位开始）：
- 结束
复杂度分析：
| 时间复杂度 | |
|---|---|
| 空间复杂度 |
分析：时间复杂度：，M是基数的个数。空间负责度：
，每个数篮子，链式存储。
2 桶排序
给定一个序列，对其进行桶排序。
算法描述：
准备：划分一定数量的桶。
- 开始：
- 遍历序列，把数放到相应的桶中；
- 对非空的同进行排序（任意排序算法）。
- 按照顺序读取桶中的元素。
- 结束
复杂度分析
| 时间复杂度 | |
|---|---|
| 空间复杂度 |
分析：N为排序长度，M为桶的个数。
- 入桶阶段，需要对每个元素划分的桶进行选择，每个元素需要比较
次；
- 排序阶段，每个桶都要进行一次排序，假设桶内元素个数均匀分布。
- 出桶阶段，每一个桶都要遍历一次。
3 计数排序
对一个给定数值上下限的序列N，对其进行计数排序。
算法描述：
准备：初始化一个全为0计数数组C。
- 遍历序列N，对于每一个遍历到的数，数组C的相应位置的值+1；
- 遍历数组C：
- 读取数组值，如果该值大于0，循环：
- 打印出该位置的编号，值-1；
- 读取数组值，如果该值大于0，循环：
- 结束算法。
复杂度分析
| 时间复杂度 | |
|---|---|
| 空间复杂度 |
分析：时间复杂度：遍历排序数组N，遍历计数数组（长度设为M），并循环N。空间复杂度：计数数组M。
可以看出，这个算法的时间复杂度是很低的，可能超过的极限。
计数排序Leetcode编程练习
