快速排序作为随机算法的一种，不能通过常规方法来计算时间复杂度
wiki上有三种快排平均时间复杂度的分析，本文记录了一种推导方法。
先放快速排序的伪代码，便于回顾、参考
quicksort(int L, int R, int array[]) {
if (L >= R) {
return;
}
int pivot = RANDOM(L, R);
int l = L, r = R;
int support_array[array.length()]
for (i = L -> R) {
if (i == pivot) {
return;
}
else if (array[i] <= array[pivot]){
support_array[l++] = array[i];
}
else {
support_array[r--] = array[i];
}
}
support_array[l] = array[pivot];
array <- support_array;
quicksort(L, l-1, array);
quicksort(l+1, R, array);
}
n为序列长度，对于长度为n的序列，我们总共需要调用n次quicksort函数，我们将序列中元素与pivot的比较操作（代码8-18行，以下简称为“比较”）提出来总体考虑，每调用一次函数，除开比较操作，时间复杂度均为O(1)，设x为n次调用函数总共的比较次数，快排的时间复杂度T(n) = O(n+x)
以下为x的计算过程
设ei为原序列中第i小的数，ej为第j小的数， j > i。在对原序列完整排序的整个过程中，每一个位置都会被选作为pivot一次。ei与ej会被比较，当且仅当在ei, ei+1, ei+2 , ... , ej-1, ej 这个子序列中（按照假设，此为非降序序列），ei与ej其中一个最先在这个子序列中被选为pivot ，否则一个大小介于他们中间的数被选为pivot，在一轮比较过后，ei和ej就会被分在两个子序列中，没有被比较且以后也不会被比较。当我们使用的生成随机数算法能保证每个数被选中为pivot的概率相等时，P(ei与ej被比较) = 2 / ( j - i + 1 )。设Y为ei与ej比较的次数，Y = 0 或 1, Y的期望计算如下
\[P(Y=1) = P(e_i与e_j被比较) = 2 / ( j - i + 1 )
\]
\]
\[E(Y) = P(Y=1) * 1 = 2 / ( j - i + 1 )
\]
\]
而在序列中，任意两项比较次数的期望均是 2 / ( j - i + 1 )
x是总共比较次数，则x的期望的表达式为
\[E(x) = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}2/(j-i+1)
\]
\]
后半部分的求和是调和级数(harmonic series)， 调和级数求和公式如下
\[1+1/2+1/3+...+1/n = ln(n+1) + γ
\]
\]
用于计算E(x)
\[\sum_{j=i+1}^{n}2/(j-i+1) = 2 * [ln(n-i+1)-1+γ] = O(logn)
\]
\]
\[E(x) = \sum_{i=1}^{n-1}O(logn) = O(nlogn)
\]
\]
\[T(n) = O(n+x) = O(n + nlogn) = O(nlogn)
\]
\]
到此，快速排序的平均时间复杂度O(nlogn)也就推导完成了。