三分钟学会快速排序（图示讲解，附代码，通俗易懂）
文章目录
tag：分治、排序
快速排序的通俗解释
1.从数组中选出一个元素 x x x(可以随意选取)
2.把所有 < = x <=x <=x的元素放在x前面（形成一个子区间），所有 > = x >=x >=x大的元素放在 x x x后面（形成另一个子区间）
3.使用递归的方法，对“2”中形成的两个子区间重复执行操作，最终可以得到一个排好序的数组
具体实现可见下面的gif图：
换句话说，快速排序就是递归的做这样一个事情：把一个区间划分为两个子区间，左区间全都
>
=
>=
>=某个特定数
x
x
x，有区间全都
>
=
>=
>=某个特定数
x
x
x。
void quick_sort(int q[], int l, int r)
{
if (l >= r)
return;//区间里面只有一个数或者没有数
int x = q[(l + r) / 2], i = l - 1, j = r + 1;//选择中间数作为标记数
while (i < j)//执行一次while语句，可以使一个区间划分为两个区间
{
do i++;while (q[i] < x);
do j--;while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q,j+1,r);
}
对上述图示与代码的解释
假设有这样一个数组q
q=[5,4,3,1];
选取中间数4作为分割区间的标记数，在初始时，i，j对应的下标分别是-1和4，如下图所示：
经过一次do while语句之后，i，j分别对应0和3，指向数组第一个和最后一个元素。
为了使前一个区间全都小于标记值4，后一个区间全都大于标记值4，我们使i++，直到i对应的值小于或等于标记值4；使j++，直到j对应的值大于或等于值4，之后进行元素值的交换（swap语句）。
通过这一次while循环，可以使得原先数组的前一半部分全部小于标记值4，后一部分全都大于标记值4。
while (i < j)//每经过一次while循环
{
do i++;while (q[i] < x);
do j--;while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
把5和1进行交换：
交换之后得到：
此时i = 0，j = 3，满足i < j，进入下一次while循环：
我们发现此时i指向4，j指向3，交换值，可以得到：
最终经过一次while循环，我们得到了基于标记值4的数组分割：即前面的数字都$<= 4 ， 后 面 的 数 字 都 4，后面的数字都 4，后面的数字都>=$4
最后递归的对这两个小区间进行快速排序，即：
quick_sort(q, l, j);
quick_sort(q,j+1,r);
算法复杂度分析
平均时间复杂度： O ( n log n ) O(n\log n) O(nlogn)
每进行一次【划分区间】操作，会递归调用处理一半大小的数列。因此，在递归结束前，我们要作 O ( log n ) O(\log n) O(logn)次嵌套的调用，即调用树的深度是 O ( log n ) O(\log n) O(logn)。程序调用的每一层次结构总共全部仅需要 O ( n ) O(n) O(n)的时间。结果是这个算法仅需使用 O ( n log n ) O(n\log n) O(nlogn)时间。
最差时间复杂度： O ( n 2 ) O(n^{2}) O(n2)
当数组已经排好序的情况下，快速排序退化为冒泡排序。
每一个区间划分成的两子区间分别含有
1
1
1 和
n
−
1
n-1
n−1个元素。第
i
i
i 次调用作了
O
(
n
−
i
)
O(n-i)
O(n−i)的工作量，且
∑
i
=
0
n
(
n
−
i
)
=
O
(
n
2
)
\sum _{i=0}^{n}(n-i)=O(n^{2})
i=0∑n(n−i)=O(n2)
递归关系式为：
T
(
n
)
=
O
(
n
)
+
T
(
1
)
+
T
(
n
−
1
)
=
O
(
n
)
+
T
(
n
−
1
)
T(n)=O(n)+T(1)+T(n-1)=O(n)+T(n-1)
T(n)=O(n)+T(1)+T(n−1)=O(n)+T(n−1)
这与插入排序与选择排序有相同的关系式，上式被解为 T ( n ) = O ( n 2 ) T(n)=O(n^{2}) T(n)=O(n2)。
c++代码
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r)
return;//区间里面只有一个数或者没有数
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
while (i < j)//每经过一次while循环
{
do i++;while (q[i] < x);
do j--;while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q,j+1,r);
}
int main()
{
cin >> n;
for (int i = 0; i < n;i++)
cin >> q[i];
quick_sort(q, 0, n - 1);
for (int i = 0;i < n;i++)
cout << q[i]<<" ";
return 0;
}