博客对您有所帮助的话，欢迎给个赞啦，你的鼓励是对我最大的支持！ 有不足之处及改进之处也请您评论指教
快速排序
下面我们介绍快速排序算法的原理及其C语言代码和Python代码实现，
1 算法思想
在待排序的初始数组 a r r arr arr中选取一个元素 (通常为第一个元素) 作为基准元素 P P P ，将数组元素划分成两个数组—— a r r 左 ， a r r 右 arr_{左}，arr_{右} arr左，arr右.
a
r
r
左
arr_{左}
arr左内的元素全小于基准元素
P
P
P.
a
r
r
右
arr_{右}
arr右内的元素全大于基准元素
P
P
P.
然后对数组
a
r
r
左
，
a
r
r
右
arr_{左}，arr_{右}
arr左，arr右分别作上述操作，直到初始数组元素全部排序完毕。
2 算法步骤
假设待排序的数组为 a r r = [ a 0 , a 1 , . . . , a n − 1 ] arr=[a_{0},a_{1},...,a_{n-1}] arr=[a0,a1,...,an−1]
首先选取
a
0
a_{0}
a0作为基准元素
P
P
P，
将
a
1
,
.
.
.
,
a
n
−
1
a_{1},...,a_{n-1}
a1,...,an−1中比
P
P
P小的全部放到
P
P
P的左边，比
P
P
P大的全部放到
P
P
P的右边.
一趟排序具体如下：
① 设置两个变量，变量1为 l o w low low，变量2为 h i g h high high, 初始时刻 l o w = 0 ， h i g h = n − 1 low = 0， high = n - 1 low=0，high=n−1;
② 以数组第一个元素为基准元素 P P P,即 P = a r r [ 0 ] P=arr[0] P=arr[0];
③ 从 h i g h high high本身开始向前搜索，找到第一个小于基准元素 P P P的值 a r r [ h i g h ] arr[high] arr[high]，接着进行 a r r [ l o w ] = a r r [ h i g h ] arr[low]=arr[high] arr[low]=arr[high];
④ 从 l o w low low本身开始向后搜索，找到第一个大于基准元素 P P P的值 a r r [ l o w ] arr[low] arr[low]，接着进行 a r r [ h i g h ] = a r r [ l o w ] arr[high]=arr[low] arr[high]=arr[low];
⑤ 重复③④直到 l o w low low等于 h i g h high high;
⑥ 划分成两个数组—— a r r 左 ， a r r 右 arr_{左}，arr_{右} arr左，arr右，对两个数组分别进行①②③④⑤，直接所有元素排序完毕。
快速排序是所有内部排序中平均性能最优的排序算法。
由于不同书籍的快排可能有些许不同(但是思想还是差不多一致)，本文选取严蔚敏的数据结构书籍为基础笔写。
3 实例
下面将某个实例和图片来介绍快速排序的思想和代码；
假设数组
a
r
r
=
[
5
,
1
,
3
,
7
,
4
,
2
,
8
,
6
]
arr=[5, 1, 3, 7, 4, 2, 8, 6]
arr=[5,1,3,7,4,2,8,6]
第一轮快排:
如下图所示，数组的初始序列为 a r r = [ 5 , 1 , 3 , 7 , 4 , 2 , 8 , 6 ] arr=[5, 1, 3, 7, 4, 2, 8, 6] arr=[5,1,3,7,4,2,8,6]，选择第一个元素5为基准元素 P （ 即 P = 5 ） P（即P=5） P（即P=5），然后第一个位置赋值为 l o w low low，最后一个位置赋值为 h i g h high high；
接着快排开始，
h
i
g
h
high
high向左搜索，找到第一个小于
P
P
P的元素并停下，并操作
a
r
r
[
l
o
w
]
=
a
r
r
[
h
i
g
h
]
arr[low]=arr[high]
arr[low]=arr[high]，然后
l
o
w
low
low指针向右搜索；
图 1 − A h i g h 指 针 左 移 图1-A ~high指针左移 图1−A high指针左移
如图1-B所示，接着上文的low指针右移，找到第一个大于P的元素并停下，并操作arr[high]=arr[low]，然后high向左搜索；
图
1
−
B
L
O
W
指
针
右
移
图1-B ~LOW指针右移
图1−B LOW指针右移
如图1-C所示，接着上文的high指针左移，找到第一个小于P的元素并停下，并操作arr[low]=arr[high]，然后low向右搜索；
图
1
−
C
h
i
g
h
指
针
左
移
图1-C ~high指针左移
图1−C high指针左移
如图1-D所示，接着上文的low指针右移，找到第一个大于P的元素并停下，但还为未发现，指针low等于high；于是arr[low]=p，于是第一轮快排结束。
图
1
−
D
l
o
w
指
针
右
移
图1-D ~low指针右移
图1−D low指针右移
如图1-D 所示，第一轮快排排序已经结束，元素5已经确定最终位置（此处可知快速排序每一趟都可以确定一个元素的最终位置），以元素5为基准，数组元素已经分为
L
左
=
【
2
，
1
，
3
，
4
】
,
L
右
=
【
7
，
8
，
6
】
L_{左}=【2， 1， 3，4】, L_{右}=【7， 8， 6】
L左=【2，1，3，4】,L右=【7，8，6】
接下来递归的对
L
左
L_{左}
L左与
L
右
L_{右}
L右进行快排操作。
按照递归操作先对 L 左 L_{左} L左，再对 L 右 L_{右} L右
对于 L 左 = 【 2 ， 1 ， 3 ， 4 】 L_{左}=【2， 1， 3，4】 L左=【2，1，3，4】按照上述的指针操作（具体操作如图2），得到 L 左 左 = 【 1 】 L_{左左}=【1】 L左左=【1】， L 左 右 = 【 3 ， 4 】 L_{左右}=【3，4】 L左右=【3，4】
图
2
对
L
左
处
理
图2~对L_{左}处理
图2 对L左处理
对于
L
左
左
=
【
1
】
L_{左左}=【1】
L左左=【1】，
L
左
右
=
【
3
，
4
】
L_{左右}=【3，4】
L左右=【3，4】,排序操作图3所示，
图
3
对
L
左
左
和
L
左
右
处
理
图3~对L_{左左}和L_{左右}处理
图3 对L左左和L左右处理
现在我们 L 左 L_左 L左处理完毕,接下来处理 L 右 L_{右} L右,处理过程如图4所示。
图
4
对
L
右
处
理
图4~对L_{右}处理
图4 对L右处理
分析可知，上述对arr数组进行快排操作分治流程过下图
图 5 a r r 数 组 分 治 过 程 图5~arr数组分治过程 图5 arr数组分治过程
4 算法分析
4.1 时间复杂度
因为快速排序每一层需要的处理的元素的时间复杂度是小于
O
(
n
)
O(n)
O(n)的；
所以总的时间复杂度为
O
(
n
∗
递
归
层
数
)
O(n*递归层数)
O(n∗递归层数)，结合递归分治流程的图以及二叉树的性质
可知：
如果划分得当（即数组第一个元素可恰好将数据中分），递归层数为
l
o
g
2
n
log_2n
log2n;
如果划分不得当（即初始数组为逆序或者顺序），递归层数为
n
n
n.
综上，快速排序的最坏时间复杂度为
O
(
n
2
)
O(n^{2})
O(n2)；
快速排序的最好时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)；
快速排序的平均时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)；
4.2 空间复杂度
同上，需要的空间辅助为递归层数的大小，
因此，快速排序的最坏空间复杂度为
O
(
n
)
O(n)
O(n)；
快速排序的最好空间复杂度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)；
快速排序的平均空间复杂度为
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)；
4.3 稳定性
不稳定
5 算法优化
通过算法分析可知，快速排序的时间和空间复杂度与分治的层数有关，而分支层数与选择的基准元素大小有关，如果选取的基准元素大小刚好能将数据中分，分治的层数就会少，快速排序的时间和空间复杂度就会降低。
因此为更好地选取可将数据进行中分的基准元素，有以下两个思想：
①从待排序数组头部、尾部及中间选取三个元素，再取三个值的中间值为基准元素
②随机地选取表中元素为基准元素
6 代码
6.1 C语言实现
#include<stdio.h>
void quick_sort(int arr[], int low, int high)
{
if(low<high)
{
int p=Partition(arr,low,high);
quick_sort(arr,low,p-1);
quick_sort(arr,p+1,high);
}
}
int Partition(int arr[], int low, int high)
{
int pivot=arr[low];
while(low<high)
{
while(low<high&&arr[high]>=pivot) high--;
arr[low]=arr[high];
while(low<high&&arr[low]<=pivot) low++;
arr[high]=arr[low];
}
arr[low]=pivot;
return low;
}
int main()
{
int arr[8]={5, 1, 3, 7, 4, 2, 8, 6};
int len=sizeof(arr)/sizeof(int);
int k;
printf("原始数组元素依次为：");
for(k=0;k<len;k++)
{
printf("%d ", arr[k]);
}
printf("\n");
quick_sort(arr, 0, len);
printf("快速排序后的数组元素依次为:");
for(k=0;k<len;k++)
{
printf("%d ", arr[k]);
}
return 0;
}
运行结果：
图
6
C
语
言
代
码
运
行
结
果
图6~C语言代码运行结果
图6 C语言代码运行结果
6.2 Python代码实现
def quick_sort(List, low, high):
''' Function description： quick sort
Parameters: List：待排序数组 low：待排序数组长度第一个位置, high：待排序数组长度最后一个位置
return: 返回已经排好序的数组
Author: kent4ngw
Address: https://blog.csdn.net/t4ngw '''
if(low < high):
p = Partition(List, low, high) # 划分左右数组
quick_sort(List, low, p-1) # 依次对左右数组递归
quick_sort(List, p+1, high)
return List
def Partition(List, low, high): # 一趟划分
pivot = List[low] # 以数组第一个元素为基准 划分数组
while(low < high): # 循环控制
while(low < high and List[high] >= pivot):
high = high - 1
List[low] = List[high] # 比基准元素小的去基准元素左边
while(low < high and List[low] <= pivot):
low = low + 1
List[high] = List[low] # 比基准元素大的去基准元素右边
List[low] = pivot
return low # 返回基准元素的位置，用来递归划分
List = [5, 1, 3, 7, 4, 2, 8, 6]
print("简单选择排序前的数组：")
print(List)
print("简单选择排序后的数组：")
print(quick_sort(List, 0, len(List)-1))
运行结果：
图
7
P
y
t
h
o
n
语
言
代
码
运
行
结
果
图7~Python语言代码运行结果
图7 Python语言代码运行结果
7 参考文献
[1]王道论坛. 2022年数据结构考研复习指导[M]. 北京:电子工业出版社, 2021.
[2]Thomas H.Cormen / Charles E.Leiserson / Ronald L.Rivest / Clifford Stein. 算法导论[M]. 原书第3版. 机械工业出版社, 2013.
写在最后面的话，此博客为个人通过书本和互联网作为学习资源自己整理而成的笔记，仅作为知识记录及后期复习所用，如有错误，还望评论指教 ——t4ngw.