No.791 快排原理以及时间复杂度，为什么（淘系前端）

快排和归排的复杂度都是O(n*log n)，为什么都用快排而不用归排？

看了《算法图解》之后，大致理解了是什么原因，真正的原因是：不可描述的常量导致使用快排而不是归排。

好了，真正的解释是这样的：

算法的每一步实际上都需要一个固定时间量，被称为常量。我们平时考虑时间复杂度的时候并不考虑常量的影响，但有时候常量的影响不可忽略，比如在这个问题上。但是大多数时候考虑复杂度的时候，可能还是不需要考虑常量的影响的，嗯，我觉得是……由于算法的每一步都有一个常量，而快排的常量比归排小，因此虽然两者的复杂度相同，但是快排更快一些。

那第二个问题就来了，归排的复杂度一直都是O(nlog n)，而快排的平均复杂度才是O(nlog n)，最坏情况下快排的复杂度可以达到O(n^2)，为什不怕快排的时候是最坏的情况呢？主要是因为绝大多数情况下，快排遇到的都是平均情况，也就是最佳情况，只有极个别的时候会是最坏情况，因此往往不考虑这种糟糕的情况。

作者：吉大秦少游 原文链接：https://blog.csdn.net/zhanshen112/article/details/85211505

其他参考：https://blog.csdn.net/qq_20746945/article/details/89378662