排序算法-线性算法(Java语言实现)
上两节中,我带你着重分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。今天,我会讲三种时间复杂度是 的排序算法:桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的,所以我们把这类排序算法叫作线性排序(Linear sort)。之所以能做到线性的时间复杂度,主要原因是,这三个算法是非基于比较的排序算法,都不涉及元素之间的比较操作。
按照惯例,我先给你出一道思考题:如何根据年龄给 100 万用户排序? 你可能会说,我用上一节课讲的归并、快排就可以搞定啊!是的,它们也可以完成功能,但是时间复杂度最低也是 O(nlogn)。有没有更快的排序方法呢?让我们一起进入今天的内