1回答

liuyubobobo

2019-02-22

已采纳

有。这个课程不涉及，有兴趣可以在网上自学一下计数排序，桶排序和基数排序。这些排序算法是O(n)的。

但是，这些排序算法并非是通用的排序算法，并不适合所有的情形，而我们在这个课程中所介绍的排序算法是通用排序算法，对于任何情形，只要你能规定出元素之间的顺序，就能进行排序。这就是Java标准库只提供O(nlogn)算法的原因。（不仅仅是Java，近乎任何语言的标准库默认都只提供O(nlogn)的排序算法。因为通用。而O(n)级别的排序算法过度依赖场景。）

具体来说，我们在这个课程中所介绍的O(nlogn)级别的算法，都被称为是“比较排序”，也就是通过不断比较两个元素之间的大小关系来逐渐完成排序的。而O(n)级别的排序算法都是“非比较排序”。已经证明的，比较类排序算法的时间最快就是O(nlogn)，而只有在场景特殊的情况下，可以积极与非比较进行排序，才能达到O(n)。具体什么叫场景特殊，怎样非比较进行排序，就不是在问答区一句话两句话可以解释清楚的了，需要深入学习理解这些非比较排序算法。依然是，如果有兴趣，可以在网上自学一下计数排序，桶排序，基数排序这些排序算法：）

另外，虽然这些非比较排序算法本身从时间复杂度分析的角度是O(n)级别的，但是由于大O时间紧复杂度，描述的是n无穷大的时候的性能趋势，面对一个具体的例子（甚至是大多数例子），O(n)级别算法不一定优于O(nlogn)的算法。如果你自学了上面这些算法，可以尝试用各种例子（比较字符串，比较数字，等等等等）测试比较一下：）

最后，我在今年上的新课，有计划系统介绍一下这些“非比较排序算法”，有兴趣的话可以期待一下：）

继续加油！：）

2

2

仙女座舜

非常感谢！

2019-02-24

共2条回复