Question

我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如图9-9-7所示，它是{50,10,90,30,70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

图9-9-7

在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为（表示不大于x的最大整数），即仅需递归log₂n次，需要时间为T(n)的话，第一次Par-tiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T(n/2)的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断。

T(n) ≤ 2T(n / 2) + n, T(1) = 0
T(n) ≤ 2(2T(n / 4) + n / 2) + n = 4T(n / 4)+2n
T(n) ≤ 4(2T(n / 8) + n / 4) + 2n = 8T(n / 8)+3n
……
T(n) ≤ nT(1) + (log2n) × n = O(nlogn)

也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为sigma(i=1, n-1, n-i)=(n-1)+(n-2)+...+1=n(n-1)/2，最终其时间复杂度为O(n²)。

平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么：

由数学归纳法可证明，其数量级为O(nlogn)。

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log₂n，其空间复杂度也就为O(logn)，最坏情况，需要进行n-1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。