3-Way快速排序的最好和最坏情况是什么？

Question

我发现在3-Way QuickSort中，最好的情况是O(n)，当每个元素相等时，最坏的情况是O(n²)，我不知道什么是O(n²)。

它是使用单轴，而不是双轴的。

我读到这篇文章的网站是：https://www.toptal.com/developers/sorting-algorithms/quick-sort-3-way。

Answer 1

找到一个中间的枢轴元素，以防止导致O(N_N)复杂度的极端枢轴情况。因此，最坏情况的复杂度被提高到O(N_logN)。3向快速排序仅适用于元素相等的情况。