关于快速排序
来源：3-5 三路快排partition思路的应用 Sort Color
cd123456
2020-06-17
波波老师，我想问下快排是无论怎么优化最坏情况都是O(nn)吗？采用三路快排+三值取中选取pivot是不是可以避免呢？三路快排可以避免数组元素全部相同的情况，三值取中对于完全排好序或近乎排好序的数组应该也不会退化到O(nn)了吧？
另外老师说java等很多语言是使用三路快排作为内置排序的算法，但我查了下好像现在java和python都是用timsort了
写回答
1回答
-
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 行。
继续加油！：）
052020-06-17
相似问题