algorithm - 快速排序的基本混淆

Question

假设我们在快速排序的情况下选择一个枢轴作为数组的第一个元素。现在最好/最坏情况的复杂性是O(n^2)，而在平均情况下是O(nlogn). 是不是很奇怪（最佳情况复杂度大于最坏情况复杂度）？

Answer 1

最好的情况复杂度是O(nlogn)，作为平均情况。最坏的情况是O(n^2)。检查http://en.wikipedia.org/wiki/Quick_sort。

虽然合并排序和堆排序等其他算法具有更好的最坏情况复杂度（O(nlogn)），但通常快速排序更快 - 这就是为什么它是最常用的排序算法。一个有趣的答案可以在为什么快速排序比合并排序更好？.

Answer 2

QuickSort的最佳案例0(nlogn)是，当所选的枢轴将子阵列分为两个 + - 同等大小的零件时。

QuickSort最坏的案例是当所选的枢轴是子阵列中最小的元素时，因此将数组分为两个部分，其中一个部分由一个元素（枢轴）和子阵列的所有其他元素组成.

因此，选择第一个元素作为已排序数组中的枢轴，将会得到0(n^2). ;)

因此，选择一个好的支点很重要。例如，通过使用子数组的第一个、中间和最后一个元素的中值作为枢轴。