快速排序是一种分治算法。选取主元后，将数组使用 partition 算法根据主元分割成两半，再对两半分别进行排序。假设左半边数量为
q
q
q，则右半边数量为
n
−
q
−
1
n-q-1
n−q−1。则由如下递归式，得到如下运行时间递归式：
T
(
n
)
=
T
(
q
)
+
T
(
n
−
q
−
1
)
+
Θ
(
n
)
T(n)=T(q)+T(n-q-1) + \Theta(n)
T(n)=T(q)+T(n−q−1)+Θ(n)
最坏情况下的复杂度显然是
T
(
n
)
=
max
0
≤
q
≤
n
−
1
(
T
(
q
)
+
T
(
n
−
q
−
1
)
)
+
Θ
(
n
)
T(n)=\max_{0\le q\le n-1}(T(q)+T(n-q-1)) + \Theta(n)
T(n)=0≤q≤n−1max(T(q)+T(n−q−1))+Θ(n)
这里使用代入法(数学归纳法)证明：假设
T
(
n
)
≤
c
n
2
T(n) \le cn^2
T(n)≤cn2 成立，代入等式右侧，原式有
T
(
n
)
≤
c
⋅
max
0
≤
q
≤
n
−
1
(
q
2
+
(
n
−
q
−
1
)
2
)
+
Θ
(
n
)
T(n) \le c\cdot \max_{0\le q\le n-1}(q^2+(n-q-1)^2) + \Theta(n)
T(n)≤c⋅0≤q≤n−1max(q2+(n−q−1)2)+Θ(n)
容易得到，
q
2
+
(
n
−
q
−
1
)
2
q^2+(n-q-1)^2
q2+(n−q−1)2 在端点取得最大值。因此：
q
2
+
(
n
−
q
−
1
)
2
≤
(
n
−
1
)
2
=
n
2
−
2
n
+
1
q^2+(n-q-1)^2\le(n-1)^2=n^2-2n+1
q2+(n−q−1)2≤(n−1)2=n2−2n+1，即
T
(
n
)
≤
c
(
n
2
−
2
n
+
1
)
+
Θ
(
n
)
≤
c
n
2
T(n) \le c(n^2-2n+1) + \Theta(n)\le cn^2
T(n)≤c(n2−2n+1)+Θ(n)≤cn2
得到上界为
O
(
n
2
)
O(n^2)
O(n2)
同理，假设
T
(
n
)
≥
c
n
2
T(n) \ge cn^2
T(n)≥cn2，使用数学归纳法也可以证明
T
(
n
)
=
Ω
(
n
2
)
T(n)=\Omega(n^2)
T(n)=Ω(n2)，因此最坏时间复杂度是
Θ
(
n
2
)
\Theta(n^2)
Θ(n2)
通过分析算法代码，可以知道，快速排序的操作主要为
对于1，易得其
≤
n
\le n
≤n。对于 2，主要看其内部循环中的比较数量
X
X
X。因此，算法的时间可以表示为
O
(
n
+
X
)
O(n+X)
O(n+X)。其中
n
n
n 在这里不重要，凑数用的。
如何计算快排的平均比较次数，即
E
(
X
)
E(X)
E(X)?
设
X
i
j
X_{ij}
Xij 为
i
i
i 与
j
j
j 是否进行了比较，比较为 1， 没比较为 0 。因为在快速排序中，两个元素之间最多比较一次（因为元素只与主元比较，而主元不参与后序的递归过程）。因此，
X
=
∑
i
=
1
n
−
1
∑
j
=
i
+
1
n
X
i
j
X= \sum_ {i=1} ^{n-1} \sum_{j=i+1}^n X_{ij}
X=∑i=1n−1∑j=i+1nXij
对其取期望，得
E
(
X
)
=
∑
i
=
1
n
−
1
∑
j
=
i
+
1
n
E
(
X
i
j
)
=
∑
i
=
1
n
−
1
∑
j
=
i
+
1
n
P
i
j
,
P
i
j
表示
i
j
发生比较的概率
E(X)= \sum_ {i=1} ^{n-1} \sum_{j=i+1}^n E(X_{ij})= \sum_ {i=1} ^{n-1} \sum_{j=i+1}^n P_{ij}, P_{ij} 表示 i j 发生比较的概率
E(X)=i=1∑n−1j=i+1∑nE(Xij)=i=1∑n−1j=i+1∑nPij,Pij表示ij发生比较的概率
为方便叙述，设
Z
Z
Z 为原数组集合的重命名，
Z
=
{
z
1
,
z
2
,
.
.
.
,
z
n
}
Z= \{z_1, z_2, ... , z_n\}
Z={z1,z2,...,zn}，其中
z
i
z_i
zi 表示数组中第
i
i
i 大值（
Z
Z
Z 就是原数组排序后重命名一下）。
如何求
i
j
i j
ij 发生比较的概率
P
i
j
P_{ij}
Pij 呢？从反向入手，什么时候
z
i
z
j
z_iz_j
zizj 不会发生比较呢？显然当
z
i
z
j
z_iz_j
zizj 之间的某一个
z
x
z_x
zx 先被选为主元之后，
z
i
z
j
z_iz_j
zizj 被分开了，所以后序的排序过程也一定不会发生比较。如果
z
i
z_i
zi 或者
z
j
z_j
zj 先被选为元素呢？那么
z
i
z
j
z_iz_j
zizj 会发生比较。如果在
[
z
i
,
z
j
]
[z_i,z_j]
[zi,zj] 以外的元素被选为主元呢？这并不重要。我们只关心
[
z
i
,
z
j
]
[z_i, z_j]
[zi,zj] 中的数，谁先被选为主元。
因此，
P
i
j
P_{ij}
Pij 的计算大大致就清楚了，其等于
[
z
i
,
z
j
]
[z_i, z_j]
[zi,zj] 中，
i
,
j
i, j
i,j 先被选为主元的概率，即
P
i
j
=
1
j
−
i
+
1
+
1
j
−
i
+
1
=
2
j
−
i
+
1
P_{ij}=\frac{1}{j-i+1}+\frac{1}{j-i+1} = \frac{2}{j-i+1}
Pij=j−i+11+j−i+11=j−i+12
代入原公式得
E
(
X
)
=
=
∑
i
=
1
n
−
1
∑
j
=
i
+
1
n
2
j
−
i
+
1
E(X)== \sum_ {i=1} ^{n-1} \sum_{j=i+1}^n \frac{2}{j-i+1}
E(X)==i=1∑n−1j=i+1∑nj−i+12
将
j
−
i
j-i
j−i 代换为
k
k
k 得
E
(
X
)
=
∑
i
=
1
n
−
1
∑
k
=
1
n
−
i
2
k
+
1
<
∑
i
=
1
n
−
1
∑
k
=
1
n
−
i
2
k
=
∑
i
=
1
n
−
1
O
(
l
g
n
)
=
O
(
n
l
g
n
)
E(X)= \sum_ {i=1} ^{n-1} \sum_{k=1}^{n-i} \frac{2}{k+1}<\sum_ {i=1} ^{n-1} \sum_{k=1}^{n-i} \frac{2}{k}=\sum_ {i=1} ^{n-1}O(lgn)=O(nlgn)
E(X)=i=1∑n−1k=1∑n−ik+12<i=1∑n−1k=1∑n−ik2=i=1∑n−1O(lgn)=O(nlgn)
再基于比较排序的下界，可知，快速排序的期望复杂度是 Θ ( n l g n ) \Theta(nlgn) Θ(nlgn)
证明完毕。