数据结构与算法：线性排序比较 _算法

文章插图
一、概述三种时间复杂度是O(n)的线性排序算法：桶排序、计数排序、基数排序。
二、相似点这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

三、适用场景桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。
四、复杂度排序算法
时间复杂度
空间复杂度
是否稳定
桶排序
O(n)
O(n)
稳定
计数排序
O(n)
O(n+k)
稳定
基数排序
O(k*n)
O(n)
稳定

【数据结构与算法：线性排序比较】