最近研究随机算法，发现快速排序作为一种入门算法，分析其时间复杂度还是很有趣的。
首先，证明其最坏时间复杂度为 是很容易的。证明其平均时间复杂度的期望是也有很多不同方式。这里介绍两种简单的方式。
需要说明的是，这里的快排是随机化的排序算法。因此对于任意输入，其期望的时间复杂度都是相同的。
首先是比较容易的方式。我们假设算法的输入是有序序列<a1,a2,a3,a4...,an>的一个排列。也就是说，我们将这个排好序的序列打乱顺序之后作为输入。算法的时间复杂度就是需要进行比较的次数。注意到一下结论：
任意两个元素至多只可能比较一次。因为比较操作是在partition时候进行的。每次比较，就说明其中一个数字是被选择作为pivot。所以，在之后的排序中，都不会再涉及pivot。两个元素会被排序的可能性与两个元素之间包含的元素个数有关。为了解释这一点，我举两个例子。 首先，考虑<a1,a2>这两个最小的元素。它们之间会进行比较的概率是1。为什么呢。因为每次选取pivot的时候，如果没有选中<a1,a2>这两个元素中的某个的时候，那它们一定会被扔到pivot的同一侧。这样，这两个元素在同一个区间里面，接下来仍然有可能被比较。如果选中了<a1,a2>，那么由于它们在同一个区间里面，因此它们一定会比较。其次，考虑a1和an。也就是最小的元素和最大的元素。它们比较的概率是2/n。因为考虑第一次选取pivot的时候。如果选中了a1和an这两个元素中的某一个，那么它们一定会比较。这样的概率是2/n。而第一次没有选取a1和an其中的某一个时，pivot一定会将这两个元素分别放在不同的递归区间里面，这样它们就不可能再被比较了。通过第二点，我们很容易想到这个结论：<ai、aj>这两个元素被比较的概率是2/(j-i+1)。为什么呢。因为排好序的序列中考虑这么一段数字<ai,ai+1,...,aj>。当选取pivot不在这个区间里面时，这段数字依然在同一个区间，也就是说接下来它们仍然有可能被比较。而当某次选取pivot在这段数字里面的时候。如果没有选<ai、aj>，那么接下来这两个数字就被放到不同区间了，不会被比较，概率是(j-i+1-2)/(j-i+1)。而选中其中一个元素，它们一定被比较，概率就是2/(j-i+1)。
所以，得到这个结论之后，一切就很简单了。用基本概率论的知识就行了。定义一个随机变量Xij，为1就说明ai和aj进行了比较，否则为0。那我们要求的就是。由Linearity of expectation，。Xij是01变量，期望就是1/j-i+1.
因此期望的时间复杂度就是 。再根据调和级数就知道，时间复杂度为O(nlog n)。
其实还有一种更简单的方法，从概率模型出发。以后再说吧。
此外，还可以证明with high probabilty，时间复杂度不会超过 c*nlog n。这也是类似的方法。以后有机会再说。