假设在快速排序的情况下，我们选择一个主元作为数组的第一个元素。现在最好/最坏情况下的复杂度是 O(n^2) 而在平均情况下它是 O(nlogn)。是不是很奇怪(最好情况的复杂度大于最坏情况的复杂度)？
最佳答案
最好的情况复杂度是 O(nlogn)，作为平均情况。最坏的情况是 O(n^2)。检查http://en.wikipedia.org/wiki/Quick_sort .
虽然合并排序和堆排序等其他算法具有更好的最坏情况复杂度 (O(nlogn))，但通常快速排序更快 - 这就是为什么它是最常用的排序算法。关于这个的有趣答案可以在 Why is quicksort better than mergesort? 找到。 .
关于algorithm - 快速排序的基本困惑，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16943860/