算法学习笔记----快速排序

一、算法描述

快速排序是一种最坏情况时间复杂度为Θ(n^2)的排序算法。虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好：它的期望时间复杂度为Θ(nlgn)，而且Θ(nlgn)中隐含的常数因子非常小。另外，它还能原址排序，甚至在虚存环境中也能很好地工作。

算法步骤如下所示：

1、将源数组A[p..r]划分为两两个子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q]，而A[q+1..r]中的每一个元素都大于A[q]，我们将这个过程称为PARTITION过程。

2、递归调用快速排序，对两个子数组分别进行快速排序

3、左右两个子数组都是排好序的，并且左边的元素总是小于等于右边的元素，所以不需要合并操作，数组A[p..r]已经是排好序的了。

二、算法实现

快速排序算法最重要的部分是将源数组划分为两个子数组的算法的实现，这直接影响快速排序算法最终的时间复杂度。下面的PARTITION实现中只使用了一个游标，可以减少在执行过程中的比较次数。快速排序的完整实现如下所示：

该递归式的解为T(n)= Θ(n^2).可以通过画递归树来证明，也可以使用代入法来证明。我们假设T(n)=Θ(n^2)是递归式的解，证明如下：

2、最好情况分析
最好的情况是每个子数组的大小都接近于数组元素个数的一半，即其中一个子数组的规模为?n/2?，另一个子数组的规模为?n/2?-1，这种情况下快速排序的性能非常好。此时的算法复杂度的递归式为：
根据主方法的情况2，递归式的解为T(n)=Θ(nlgn)。
快速排序算法的平均运行时间更接近于其最好情况，只要划分是常数比例的，算法的运行时间总是Θ（nlgn）。即使划分产生9:1的划分，也是如此，通过画递归树很容易证明该结论。