排序算法三（桶，计数，基数）

桶排序，计数排序，基数排序算法的时间复杂度都是线性的，所以把这类排序算法叫作线性排序。

桶排序

概念：将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序后，再把每个桶的数据按照顺序依次取出，组成的序列就是有序的了。

时间复杂度：假如要排序的n个数据，均匀划分到m个桶内，每个桶里就有n/m个元素。每个桶内部使用快速排序，时间复杂度=O(n/m*log(n/m))。m个桶排序的时间复杂度=O(n*log(n/m))，当桶的个数m接近个数n时，log(n/m)就是一个常量，所以时间复杂度解决O(n)。

场景：要排序的数据需要很容易就能划分为m个桶，桶与桶之间有着天然的大小顺序。其次，数据在各个桶之间的分布是比较均匀的。最差情况可能直接退化为O(nlogn)。桶排序比较适合用在外部排序中。所谓外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。就可以把数据量按照桶分离，直至内存能够存储每个桶的数据大小。

计数排序

计数排序是一种特殊的桶排序。也是分为m个桶，每个桶放入大小相等的数据。可知计数排序和桶排序应用场景都是在：数据的个数很多，但是数据的范围很小的场景，如统计100万人年龄的排序等。

限制：只能用在数据范围不大的场景中，而且计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

show me code:

基数排序

概念：对要排序数据，从低位向高位，进行排序。

约束：基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。