java - 修改后的快速排序可以是 O(n) 的最佳情况吗？

Question

人们普遍认为快速排序的最佳情况是 O(nlogn)，因为数组每次大约被分成一半。也有人说，假设数组已排序，最坏情况是 n^2 阶。

我们不能通过设置一个名为 swap 的 boolean 值来修改快速排序吗？例如，如果第一次遍历时没有初始交换位置，那么我们可以假设数组已经排序，因此不要进一步划分数据。

我知道修改后的冒泡排序通过检查交换来使用它，允许最好的情况是 O(n) 而不是 O(n^2)。这种方法可以应用于快速排序吗？为什么或为什么不？

Answer 1

您的方法有一个错误...例如我们有一个这样的数组:1243 5 678

我们的枢轴元素是 5。第一次通过后不会有交换(因为 4 和 3 都较小)，但数组未排序。所以你必须开始将它除以 n log n。