练习解答链接：https://ita.skanev.com/

快速排序的时间复杂度：

最坏情况下时间复杂度为：

期望时间复杂度：

平均性能比较好，能够原址排序！

快速排序描述：

快速排序只要主要分治+递归的思想进行排序。

主要有以下三个步骤：

输入数据：待排序的数组A[p....r]。

1.分区过程：将A[p....r]分成两个新数组A[p....q-1]，A[q+1,r]和一个中间值A[q]。保证A[p....q-1]中所有值小于A[q]，A[q+1,r]中所有值大于A[q]。注：A[q]不一定非得是中间值。

2.递归调用以上分区过程。

3.合并，事实上没有这一个步骤，因为经过上述步骤就已经完成了排序。

下面详细介绍一下数组的分区步骤：

分区步骤的算法复杂度是：

数组A[p..r]分区的算法复杂度是,其中n=r-p+1。

快速排序的性能

性能取决于划分是否平衡

1.当划分是处于最大不平衡状态下式算法的时间复杂度是：,运行时间并不比插入排序好；

2.当输入数组处于完全有序的情况下，快速排序的算法复杂度是，与此同时插入排序的算法复杂度是

3.最好的情况下，分区得到的两个新数组均不大于n/2,算法时间复杂度为(分治算法的时间复杂度为lgn)

4.任何一种常数比例的划分（即使看起来十分不平衡，即比如每次9：1划分），最后的时间复杂度仍然是

5.当好的情况和坏的情况交叉出现时，快速排序的时间复杂度和全是好的时候是一样的，仍然是。

快速排序的随机化版本

有时输入数据是有序的（最坏情况下），所以需要在算法中引入随机性，从而使算法对于所有的输入都能获得较好的期望性能。

随机化版本会在A[p...r]中随机抽取一个作为主元，而不是将A[r]作为主元，通知还需要将随机抽取的主元与A[r]对调。改动非常之小！