O（n）的快速排序的最佳情况是什么？

Question

您能否解释在最佳情况下如何对O（N）进行快速排序？为什么会有O（N）？

Answer 1

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

假设一个数组，其中每个元素都相等。基于c ++中的this实现，partition函数将仅被调用一次，因为所有元素都位于中间分区（与数据透视表相等），因此将来的quicksort函数调用将无法满足if条件。