| 时间复杂度 | |
|---|---|
| 桶排序 | n |
| 计数排序 | n |
| 基数排序 | $ d * (n + r) $ |
这三种排序算法对排序的数据要求都很严苛。它们的时间复杂度都是线性的，所以这类排序算法又被叫作线性排序。
桶排序
核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据单独再进行排序。桶内排序完之后，再把每个桶里的数据按照顺序依次取出。
桶排序时间复杂度计算
如果要排序的数据有n个，我们把他们均匀地划分到m个桶内，每个桶里就有k = n / m个元素。每个桶内部使用快速排序，时间复杂度为O(n*log(n/m))。当桶的个数m接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。
桶排序的应用场景
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
计数排序
可以认为，计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据分成k个桶。每个桶内的数据值都是相同的。
计数排序的局限性
计数排序只能用在数据范围不到的场景中，如果数据范围k比排序的数据n大得多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
基数排序
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大。
假设有n条数据，数据的长度为d，数据每一位的基数为r（比如对于10进制数，则有r=10）。那么我们会进行d趟操作，每趟排序操作分为两个步骤（假设当前第一趟）：
- 1、分配，遍历n条数据的最高位进行分配，将数据分配到r个桶中，那么一趟的时间复杂度为O(n)
- 2、收集，将r个桶的数据归集起来，时间复杂度为O(r)