一般认为,快速排序的最佳情况是O(nlogn),假设每次分区时数组大致上被划分了一半。同时,最坏情况是n^2阶,如果数组已经被排序。我们能不能通过设置一个名为swap的布尔值来修改快速排序呢?例如,如果第一次遍历中没有初始交换位置,那么我们可以假设数组已经被排序,因此不需要进一步分区数据。我知道改进后的冒泡排序使用了这种方法,通过检查交换,让最佳情况变成了O(n),而不是O(n^2)。这种方法能否应用于快速排序呢?为什么?
你的方法有一个错误...
例如我们有这样一个数组:
1243 5 678
我们的基准元素是 5。第一次遍历后不会进行交换(因为4和3都比它小),但是数组并没有排序。所以你必须开始划分,这导致了n log n的时间复杂度。