- 内部排序之快速排序法
- 主要思想
- 过程演示
- JAVA代码
- 算法分析
- 时间复杂度分析
- 最好时间复杂度
- 最坏时间复杂度
- 平均时间复杂度
- 空间复杂度
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
通过一趟排序将待排记录分割成独立的两个部分，一部分的关键字比另一部分的关键字小，则可以分别对两部分记录继续进行排序。
- 选取任务选取的一个记录，作为枢轴或（支点）（pivot）
- 重新排列记录，所有关键字比pivot值小的摆放在pivot前面，所有关键字比pivot值大的摆在pivot的后面（相同的数可以到任一边）。在这个分区退出之后，该pivot就处于数列的中间位置。这个称为分区（partition）操作；
- 重复执行步骤2。把小于pivot关键字的子数列和大于pivot关键字的子数列排序。
package sort;
public class QuickSort {
private static int count = 1;
public static void main(String[] args) {
int[] o = {49, 38, 45, 27, 46, 13, 27, 8};
System.out.print("排序前: ");
for (int t : o) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
// 算法部分
int left = 0;
int right = o.length - 1;
quickSort(o, left, right);
System.out.print("排序后: ");
for (int t : o) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
}
private static void quickSort(int[] arr, int left, int right) {
if (left 1 其中
D
(
n
)
=
n
−
1
D(n)=n−1
D(n)=n−1 ,是一趟快排需要的比较次数，一趟快排结束后将数组分成两部分
I
1
I_1
I1 和
I
2
I_2
I2。
最好时间复杂度
最好的情况是，每一次划分都正好将数组分成长度相等的两半
T
(
n
)
=
{
D
(
1
)
n
≤
1
D
(
n
)
+
T
(
n
2
)
+
T
(
n
2
)
n
>
1
T(n)= \begin{cases} D(1) & {n \leq 1} \\ D(n)+T(\frac{n}{2})+T(\frac{n}{2}) &{n >1 } \end{cases}
T(n)={D(1)D(n)+T(2n)+T(2n)n≤1n>1
∴
T
(
n
)
=
D
(
n
)
+
2
T
(
n
2
)
=
D
(
n
)
+
2
D
(
n
2
)
+
2
T
(
n
4
)
.
.
.
=
D
(
n
)
+
2
D
(
n
2
)
+
4
D
(
n
4
)
+
.
.
.
+
2
k
D
(
n
2
k
)
=
n
−
1
+
2
(
n
2
−
1
)
+
4
(
n
4
−
1
)
+
.
.
.
+
2
k
(
n
2
k
−
1
)
=
(
n
−
1
)
+
(
n
−
2
)
+
(
n
−
4
)
+
.
.
.
+
(
n
−
2
k
)
⟹
∑
k
=
1
n
n
−
2
k
=
k
n
−
2
k
+
1
∵
k
=
l
o
g
2
n
∴
原式
=
n
l
o
g
2
n
−
2
n
+
1
⟹
O
(
n
l
o
g
2
n
)
\begin{aligned} \therefore T(n)&=D(n)+2T(\frac{n}{2}) \\ &=D(n)+2D(\frac{n}{2})+2T(\frac{n}{4}) \\ &.\\ &.\\ &.\\ &=D(n)+2D(\frac{n}{2})+4D(\frac{n}{4})+...+2^kD(\frac{n}{2^k}) \\ &=n-1+2(\frac{n}{2}-1)+4(\frac{n}{4}-1)+...+2^k(\frac{n}{2^k}-1) \\ &=(n-1)+(n-2)+(n-4)+...+(n-2^k) \\ &\implies \displaystyle \sum_{k=1}^{n} n-2^k=kn-2^k+1 \\ &\because k=log_2^n\\ &\therefore 原式=nlog_2^n-2n+1 \implies \boxed{O(nlog_2^n)}\\ \end{aligned}
∴T(n)=D(n)+2T(2n)=D(n)+2D(2n)+2T(4n)...=D(n)+2D(2n)+4D(4n)+...+2kD(2kn)=n−1+2(2n−1)+4(4n−1)+...+2k(2kn−1)=(n−1)+(n−2)+(n−4)+...+(n−2k)⟹k=1∑nn−2k=kn−2k+1∵k=log2n∴原式=nlog2n−2n+1⟹O(nlog2n)
最坏时间复杂度
最坏情况下，每一次划分都将数组分成了
0
0
0和
n
−
1
n-1
n−1两部分
T
(
n
)
=
{
D
(
1
)
n
≤
1
D
(
n
)
+
T
(
n
−
1
)
+
T
(
0
)
n
>
1
T(n)= \begin{cases} \vcenter D(1) &{n \leq 1} \\ D(n)+T(n-1)+T(0) &{n >1 } \end{cases}
T(n)={D(1)D(n)+T(n−1)+T(0)n≤1n>1
∴
T
(
n
)
=
D
(
n
)
+
2
T
(
n
−
1
)
=
D
(
n
)
+
D
(
n
−
1
)
+
T
(
n
−
2
)
.
.
.
=
D
(
n
)
+
D
(
n
−
1
)
+
D
(
n
−
2
)
+
.
.
.
+
D
(
1
)
=
(
n
−
1
)
+
(
n
−
2
)
+
(
n
−
3
)
+
.
.
.
+
0
⟹
∑
k
=
0
n
k
=
n
(
n
−
1
)
2
原式
=
n
(
n
−
1
)
2
⟹
O
(
n
2
)
\begin{aligned} \therefore T(n)&=D(n)+2T(n-1) \\ &=D(n)+D(n-1)+T(n-2) \\ &.\\ &.\\ &.\\ &=D(n)+D(n-1)+D(n-2)+...+D(1) \\ &=(n-1)+(n-2)+(n-3)+...+0 \\ &\implies \displaystyle \sum_{k=0}^{n}k=\frac{n(n-1)}{2} \\ 原式&=\frac{n(n-1)}{2} \implies \boxed{O(n^2)}\\ \end{aligned}
∴T(n)原式=D(n)+2T(n−1)=D(n)+D(n−1)+T(n−2)...=D(n)+D(n−1)+D(n−2)+...+D(1)=(n−1)+(n−2)+(n−3)+...+0⟹k=0∑nk=2n(n−1)=2n(n−1)⟹O(n2)
平均时间复杂度
任意一种划分情况出现的概率都相等
A
l
l
=
{
I
1
=
0
I
2
=
n
−
1
I
1
=
1
I
2
=
n
−
2
.
.
.
I
1
=
n
−
1
I
2
=
0
All= \begin{cases} I_1=0 & I_2=n-1 \\ I_1=1 & I_2=n-2 \\ . \\ . \\ . \\ I_1=n-1 & I_2=0 \\ \end{cases}
All=⎩
⎨
⎧I1=0I1=1...I1=n−1I2=n−1I2=n−2I2=0
∴
T
a
v
g
(
n
)
=
D
(
n
)
+
1
n
∗
∑
i
=
0
n
−
1
T
a
v
g
(
i
)
+
T
a
v
g
(
n
−
i
)
=
D
(
n
)
+
2
n
∗
∑
i
=
0
n
−
1
T
a
v
g
(
i
)
T
a
v
g
(
n
−
1
)
=
D
(
n
−
1
)
+
2
n
−
1
∗
∑
i
=
0
n
−
2
T
a
v
g
(
i
)
n
T
a
v
g
(
n
)
−
(
n
−
1
)
T
a
v
g
(
n
−
1
)
=
n
D
(
n
)
+
2
∑
i
=
0
n
−
1
T
a
v
g
(
i
)
−
(
n
−
1
)
D
(
n
−
1
)
−
2
∗
∑
i
=
0
n
−
2
T
a
v
g
(
i
)
=
n
D
(
n
)
−
(
n
−
1
)
D
(
n
−
1
)
+
2
T
a
v
g
(
n
−
1
)
=
n
(
n
−
1
)
−
(
n
−
1
)
(
n
−
2
)
+
2
T
a
v
g
(
n
−
1
)
=
2
(
n
−
1
)
+
2
T
a
v
g
(
n
−
1
)
移项得
n
T
a
v
g
(
n
)
=
2
(
n
+
1
)
+
2
T
a
v
g
(
n
−
1
)
+
(
n
−
1
)
2
T
a
v
g
(
n
−
1
)
=
2
(
n
+
1
)
+
(
n
+
1
)
2
T
a
v
g
(
n
−
1
)
等式两边同时除以
n
(
n
+
1
)
得
T
a
v
g
(
n
)
n
+
1
=
T
a
v
g
(
n
−
1
)
n
+
2
(
n
−
1
)
n
(
n
+
1
)
令
B
(
n
)
=
T
a
v
g
(
n
)
n
+
1
得
B
(
n
)
=
B
(
n
−
1
)
+
2
(
n
−
1
)
n
(
n
+
1
)
=
B
(
n
−
2
)
+
2
(
n
−
2
)
n
(
n
−
1
)
+
2
(
n
−
1
)
n
(
n
+
1
)
.
.
.
=
B
(
1
)
+
∑
i
=
1
n
2
(
i
−
1
)
i
(
i
+
1
)
=
B
(
1
)
+
∑
i
=
1
n
2
(
i
+
1
)
−
4
i
(
i
+
1
)
=
∑
i
=
1
n
[
2
i
−
4
i
(
i
+
1
)
]
∵
∑
i
=
1
n
4
i
(
i
+
1
)
=
4
∑
i
=
1
n
[
i
+
1
−
i
i
(
i
+
1
)
]
=
4
∑
i
=
1
n
[
1
i
−
1
i
(
i
+
1
)
]
=
4
[
1
−
1
n
+
1
]
=
4
n
n
+
1
∵
∑
i
=
1
n
1
i
≈
0.577216+ln(n)
∴
B
(
n
)
=
2
∗
0.577216
+
2
∗
l
n
(
n
)
+
4
n
n
+
1
代回
B
(
n
)
=
T
a
v
g
(
n
)
n
+
1
T
a
v
g
(
n
)
=
2
(
n
+
1
)
l
n
(
n
)
−
4
n
+
2
∗
0.577216
(
n
+
1
)
⟹
O
(
n
l
o
g
2
n
)
\begin{aligned} \therefore T_{avg}(n)&=D(n)+\frac{1}{n}*\displaystyle \sum_{i=0}^{n-1}T_{avg}(i)+T_{avg}(n-i) \\ &=D(n)+\frac{2}{n}*\displaystyle \sum_{i=0}^{n-1}T_{avg}(i) \\ T_{avg}(n-1)&=D(n-1)+\frac{2}{n-1}*\displaystyle \sum_{i=0}^{n-2}T_{avg}(i)\\ nT_{avg}(n)-(n-1)T_{avg}(n-1)&= nD(n)+2\displaystyle \sum_{i=0}^{n-1}T_{avg}(i)-(n-1)D(n-1)-2*\displaystyle \sum_{i=0}^{n-2}T_{avg}(i) \\ &=nD(n)-(n-1)D(n-1)+2T_{avg}(n-1) \\ &=n(n-1)-(n-1)(n-2)+2T_{avg}(n-1) \\ &=2(n-1)+2T_{avg}(n-1) \\ 移项得 \\ nT_{avg}(n) &= 2(n+1)+2T_{avg}(n-1)+(n-1)2T_{avg}(n-1) \\ &= 2(n+1)+(n+1)2T_{avg}(n-1) \\ 等式两边同时除以n(n+1)得 \\ \frac{T_{avg}(n)}{n+1}&=\frac{T_{avg}(n-1)}{n}+\frac{2(n-1)}{n(n+1)} \\ 令B(n)=\frac{T_{avg}(n)}{n+1} 得\\ B(n)&=B(n-1)+\frac{2(n-1)}{n(n+1)} \\ &=\boxed{B(n-2)+\frac{2(n-2)}{n(n-1)}}+\frac{2(n-1)}{n(n+1)} \\ .\\ .\\ .\\ &=B(1)+\displaystyle \sum_{i=1}^{n}\frac{2(i-1)}{i(i+1)} \\ &=B(1)+\displaystyle \sum_{i=1}^{n}\frac{2(i+1)-4}{i(i+1)} \\ &=\displaystyle \sum_{i=1}^{n}[\frac{2}{i}-\frac{4}{i(i+1)}] \\ \because \displaystyle \sum_{i=1}^{n}\frac{4}{i(i+1)}&= 4\displaystyle \sum_{i=1}^{n}[\frac{i+1-i}{i(i+1)}] \\ &= 4\displaystyle \sum_{i=1}^{n}[\frac{1}{i}-\frac{1}{i(i+1)}] \\ &= 4[1-\frac{1}{n+1}]=\boxed{4\frac{n}{n+1}}\\ \because \displaystyle \sum_{i=1}^{n}\frac{1}{i}&\approx \colorbox{aqua}{0.577216+ln(n)} \\ \therefore B(n)&=2*0.577216+2*ln(n)+4\frac{n}{n+1} \\ 代回B(n)=\frac{T_{avg}(n)}{n+1} \\ T_{avg}(n)&=2(n+1)ln(n)-4n+2*0.577216(n+1) \implies \boxed{O(nlog_2^n)} \\ \end{aligned}
∴Tavg(n)Tavg(n−1)nTavg(n)−(n−1)Tavg(n−1)移项得nTavg(n)等式两边同时除以n(n+1)得n+1Tavg(n)令B(n)=n+1Tavg(n)得B(n)...∵i=1∑ni(i+1)4∵i=1∑ni1∴B(n)代回B(n)=n+1Tavg(n)Tavg(n)=D(n)+n1∗i=0∑n−1Tavg(i)+Tavg(n−i)=D(n)+n2∗i=0∑n−1Tavg(i)=D(n−1)+n−12∗i=0∑n−2Tavg(i)=nD(n)+2i=0∑n−1Tavg(i)−(n−1)D(n−1)−2∗i=0∑n−2Tavg(i)=nD(n)−(n−1)D(n−1)+2Tavg(n−1)=n(n−1)−(n−1)(n−2)+2Tavg(n−1)=2(n−1)+2Tavg(n−1)=2(n+1)+2Tavg(n−1)+(n−1)2Tavg(n−1)=2(n+1)+(n+1)2Tavg(n−1)=nTavg(n−1)+n(n+1)2(n−1)=B(n−1)+n(n+1)2(n−1)=B(n−2)+n(n−1)2(n−2)+n(n+1)2(n−1)=B(1)+i=1∑ni(i+1)2(i−1)=B(1)+i=1∑ni(i+1)2(i+1)−4=i=1∑n[i2−i(i+1)4]=4i=1∑n[i(i+1)i+1−i]=4i=1∑n[i1−i(i+1)1]=4[1−n+11]=4n+1n≈0.577216+ln(n)=2∗0.577216+2∗ln(n)+4n+1n=2(n+1)ln(n)−4n+2∗0.577216(n+1)⟹O(nlog2n)
空间复杂度
快速排序的空间复杂度取决于分划基准的选择，每次都选在中间，
O
(
l
o
g
2
n
)
O(log_2^n)
O(log2n)若基本有序，退化为冒泡，栈的深度
O
(
n
)
O(n)
O(n)。
O
(
l
o
g
2
n
)
O(log_2^n)
O(log2n)就是递归的深度，递归的时候使用的栈空间稍微优化一点的快排，比如取首尾中三个数据，取其中间的值作为划分标准，不会出现退化到冒泡的可能。
计算参考：https://zhuanlan.zhihu.com/p/341201904
