关于快速排序

Question

波波老师，我想问下快排是无论怎么优化最坏情况都是O(nn)吗？采用三路快排+三值取中选取pivot是不是可以避免呢？三路快排可以避免数组元素全部相同的情况，三值取中对于完全排好序或近乎排好序的数组应该也不会退化到O(nn)了吧？
另外老师说java等很多语言是使用三路快排作为内置排序的算法，但我查了下好像现在java和python都是用timsort了

Answer 1

liuyubobobo 2020-06-17 14:34:28

1 

是的，三路快排无论怎么优化，最坏时间复杂度都是 O(nlogn) 的

2 

在所有元素都一样的情况下，三路快排是 O(n) 的。但是，我们不是以某一种特殊情况来看某个算法的时间复杂度的，而是最坏情况，所以三路快排依然是 O(nlogn) 的算法。这就像插入排序在全部数据有序的情况下是 O(n) 的，但是插入排序算法还是一个 O(n^2) 的算法。

3 

Java 中的 Arrays.sort 默认是三路快排（但和课程中介绍的三路快排还有一定区别。）可以参考这里：http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/be44bff34df4/src/share/classes/java/util/Arrays.java 143 行。

继续加油！：）

• 提问者 cd123456 #1

  “是的，三路快排无论怎么优化，最坏时间复杂度都是 O(nlogn) 的” 波波老师是不是写错了？最坏是不是O(n^2)呢

• liuyubobobo 回复 提问者 cd123456 #2

  不是。就是nlogn。这里有快速排序的特殊之处。我们通常不会去看随机选择的 pivot 永远是在一端的这种极端情况，因为他出现的概率太低了。所以，通常我们说快速排序的时间复杂度，说的是期望值，因为他本身是一个随机算法。注意，这和其他算法，我们能稳定找到一组数据，这组数据 100% 的会让算法退化，是有区别的。

• 提问者 cd123456 回复 liuyubobobo #3

  好的明白了谢谢波波老师~老师回复的太快了

点开查看后面2条评论