桶排序(Bucket sort)
特点
将数据拆分到几个有序的桶里，每个桶里的数据再单独进行排序
桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列即为有序
复杂度分析
最好情况时间复杂度: O(n)
最坏情况时间复杂度:O(nlogn)
平均情况时间复杂度:O(n)
待排序数据有n个，把它们均匀地划分到m个桶内，每个桶里就有k=n/m个元素
每桶内部使用快排，时间复杂度为O(k*logk)，整个桶排序时间复杂度为O(m* k*logk)
因k=n/m，所以整个桶排序时间复杂度为O(n*log(n/m))。
当桶的个数m接近数据个数n时，log(n/m)为非常小常量，桶排序时间复杂度接近O(n)
前提条件
首先，要排序的数据要很容易能划分成m个桶，并且桶与桶之间有着天然的大小顺序
其次，数据在各个桶之间的分布是比较均匀，否则极端情况下时间复杂度降为O(nlogn)
应用场景
桶排序比较适合用在外部排序中
数据量大且内存有限，将数据存储在外部磁盘，加载部分数据到内存进行排序再合并
计数排序(Counting sort)
特点
计数排序其实是桶排序的⼀种特殊情况。跟桶排序⾮常类似，只是桶的⼤⼩粒度不⼀样
排序过程
待排序的N(数值不大)个数据,最大值是K，我们就数据划分成K个桶
每个桶内的数据值都是相同的，省掉了桶内排序的时间。
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
不是原地排序算法
需借助额外存储空间
稳定的排序算法
时间复杂度
最好/最坏/平均情况时间复杂度: O(n)
总结
计数排序只能⽤在数据范围不⼤的场景中，如果数据范围k⽐要排序的数据n⼤很多，就不适合⽤计数排序了。
⽽且，计数排序只能给⾮负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对⼤⼩的情况下，转化为⾮负整数。
基数排序(Radix sort)
特点
原地排序算法
稳定排序算法
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
基数排序基于固有顺序,所以属于稳定排序算法
排序过程
取数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
时间复杂度
时间复杂度为: O(k*n)，其中k为数组中的数的最大的位数，基数排序的时间复杂度就近似于O(n)
总结
基数排序要求数据可以划分成高低位，位之间有递进关系
例如:有如下5组单词: hke、iba、hzg、ikf、hac，按照字母从a-z排序，具体如下:
