algorithm - O(n) 的快速排序的最佳情况是什么？

Question

你能解释一下在最好的情况下如何对 O(N) 进行快速排序吗？为什么会有O(N)？

Answer 1

快速排序的最佳情况是O(nlogn). 当您使用 3 路快速排序时，最好的情况是 O(n)。

假设一个数组，其中每个元素都相等。基于c++中的这种partition实现，函数只会被调用一次，因为所有元素都放在中间分区，等于pivot，那么以后调用quicksort函数就不会满足if条件了。