博客对您有所帮助的话，欢迎给个赞啦，你的鼓励是对我最大的支持！ 有不足之处及改进之处也请您评论指教
快速排序
1 算法思想2 算法步骤3 实例4 算法分析
4.1 时间复杂度4.2 空间复杂度4.3 稳定性 5 算法优化6 代码
6.1 C语言实现6.2 Python代码实现 7 参考文献
下面我们介绍快速排序算法的原理及其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右分别作上述操作，直到初始数组元素全部排序完毕。
假设待排序的数组为 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右，对两个数组分别进行①②③④⑤，直接所有元素排序完毕。
快速排序是所有内部排序中平均性能最优的排序算法。
由于不同书籍的快排可能有些许不同(但是思想还是差不多一致)，本文选取严蔚敏的数据结构书籍为基础笔写。
下面将某个实例和图片来介绍快速排序的思想和代码；
假设数组
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)；
同上，需要的空间辅助为递归层数的大小，
因此，快速排序的最坏空间复杂度为 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)；
不稳定
5 算法优化通过算法分析可知，快速排序的时间和空间复杂度与分治的层数有关，而分支层数与选择的基准元素大小有关，如果选取的基准元素大小刚好能将数据中分，分治的层数就会少，快速排序的时间和空间复杂度就会降低。
因此为更好地选取可将数据进行中分的基准元素，有以下两个思想：
①从待排序数组头部、尾部及中间选取三个元素，再取三个值的中间值为基准元素
②随机地选取表中元素为基准元素
6 代码 6.1 C语言实现#include
运行结果：
图 6 C 语 言 代 码 运 行 结 果 图6~C语言代码运行结果 图6 C语言代码运行结果
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 Listdef 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语言代码运行结果
[1]王道论坛、2022年数据结构考研复习指导[M]、北京:电子工业出版社, 2021.
[2]Thomas H.Cormen / Charles E.Leiserson / Ronald L.Rivest / Clifford Stein、算法导论[M]、原书第3版、机械工业出版社, 2013.
写在最后面的话，此博客为个人通过书本和互联网作为学习资源自己整理而成的笔记，仅作为知识记录及后期复习所用，如有错误，还望评论指教 ——t4ngw.