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