就地快速排序的时间复杂度是多少？

Question

我知道空间复杂度从O(n)下降到O(log )。但是时间复杂度又如何呢？执行Quick Sort的时间是否与常规版本相同？

Answer 1

快速排序是一种递归的就地排序算法，你问这个问题是什么意思？没有快速排序的非就地版本。由于它是一个递归的divide-et-impera算法，因此很容易证明，正如您所说的那样，空间复杂度至少为O(log )。如上所述，如果使用迭代实现，空间完备度将为O(1)。

算法的平均复杂度为O(n log )，在默认实现中为O(n*n)最坏情况。最坏的情况是列表已经排序。

相反，合并排序是O(n log n)最坏情况，但由于常量较大，通常比快速排序慢。同样，合并排序的空间复杂度为O(log )。

Answer 2

已经有了运行在O(nlogn)最坏情况下的QuickSort实现，对于你的问题，没有比O(nlogn)基于最坏情况比较的排序更好的了，并且当快速排序为1时，证明了O(nlogn)无论如何都是不可击败的。

我所知道的QuickSort的唯一实现是就地实现的，但无论如何，你能改进的就是快速排序的常量，除了你提到的，所需的空间可以减少到O(1) (迭代版本)和O(logn)在递归版本中。