快速排序

对于输入规模是n的数组，快速排序是一种最坏情况时间复杂度是 )的排序算法。虽然最坏情况的时间复杂度很差，但是快速排序通常是实际排序中最好的选择，因为平均性能非常好。

描述

快速排序也使用了分治法的思想。
下面是对一个典型的子数组A[p,..,r]进行快速排序的三步分治过程：

• 分解：将数组A[p,..,r]划分为两个子数组A[p,..,q-1]和A[q+1,..,r]，使得前一个子数组中每一个元素都小于等于A[q]，后面子数组中每一个元素都大于等于A[q]，其中，计算q也是划分过程的一部分。
• 解决：通过递归调用快速排序，对子数组进行排序。
• 合并：子数组是原址排序所有不需要合并。

下面的伪代码实现快速排序：

QUICKSORT(A,p,r)

if p<r
    q=PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)

下面的伪代码实现数组的划分：

PARTITION(A,p,r)

x=A[r]
i=p-1
for j=p to r-1
    if A[j]<=x
        i++
        exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1

快速排序的性能

最坏情况

当划分产生的两个子问题分别包含了n-1个元素和0个元素时，时间复杂度是 )。此外在输入数组完全有序的时候，快速排序的时间复杂度依然是 )，而在同样的情况下，插入排序是  )

最好情况

在可能的最平衡的划分中，得到的两个子问题的规模都不大于n/2。在这种情况下，快速排序的性能非常好。时间复杂度是 )

平衡的划分

快速排序的平均时间更接近于最好情况。理解这一点的关键及时理解划分的平衡性是如何反映到描述运行时间的递归式上的。事实上，任何一种常数比例的划分都会产生深度为 )的递归树，其中每一层的代价都是 )。因此，只要划分是常数比例的，算法的运行时间总会 )