QuickSort

Posted on |

快速排序

时间复杂度分析

最坏情况划分

当划分产生的两个子问题分别包含了n-1和0个元素时，快速排序的最坏情况发生。不妨假设算法的每一次递归中都出现了这种不平衡划分。

  • 划分的操作时间复杂度是O(n)
  • 对大小为0的数组进行递归调用回直接返回，时间复杂度是T(0)=1

算法运行时间的递归式可以表示为
从直观上看，每层递归的代价可以被累加起来，从而得到一个算术级数$\sum_{k=1}^{n} {k}=\frac 1 2 n(n-1)$，其结果是$O(n^2)$

最好情况划分

在可能的最平衡划分中，Partition得到两个子问题的规模都不大于$n/2$，其中一个子问题的规模是$[n/2]$，另一个子问题的规模是$[n/2]-1$。

算法运行时间的递归式是
根据主定理的情况2，上述递归式的解为$T(n)=O(n \lg n)$

平衡的划分

任何一个常熟比例的划分都会产生深度为$O( \lg n)$的递归树，其中每一层的时间代价都是O(n)。因此，只要划分是常数比例，算法运行时间总是$O( \lg n)$

对于平均情况的直观观察

当好和差划分交替出现时，快速排序的时间复杂度与全是好的划分时一样，仍然是$O(\lg n)$，区别在于O符号中隐含的常数因子要略大一些

  • 如果算法的每一层递归上，划分都是最大程度的不平衡，算法的时间复杂度是$O(n^2)$
  • 如果算法的每一层递归上，划分都是最大程度的平衡，算法的时间复杂度是$O(n\lg n)$
  • 只要划分是常数比例，算法运行时间总是$O(\lg n)$

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def Partition(A,p,r):
    x=A[r]
    i=p-1

    for j in range(p,r):
        if A[j]<=x:
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1

def QuickSort(A,p,r):
    if p<r:
        q=Partition(A,p,r)
        QuickSort(A,p,q-1)
        QuickSort(A,q+1,r)
    return A

if __name__=='__main__':
    import random
    A=[random.randint(0,100) for i in range(10)]
    print("Now displaying QuickSort")
    print('Unsorted sequence:\t', A)
    print('Sorted sequence:\t', QuickSort(A, 0, len(A) - 1))

    # Now displaying QuickSort
    # Unsorted sequence:	 [35, 92, 92, 80, 79, 13, 40, 92, 89, 61]
    # Sorted sequence:	 [13, 35, 40, 61, 79, 80, 89, 92, 92, 92]