博客对您有所帮助的话，欢迎给个赞啦，你的鼓励是对我最大的支持！ 有不足之处及改进之处也请您评论指教

快速排序

• • 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右​分别作上述操作，直到初始数组元素全部排序完毕。

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 log2​n;
如果划分不得当（即初始数组为逆序或者顺序），递归层数为 n n n.

综上，快速排序的最坏时间复杂度为 O ( n 2 ) O(n^{2}) O(n2)；
快速排序的最好时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)；
快速排序的平均时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)；

4.2 空间复杂度

同上，需要的空间辅助为递归层数的大小，
因此，快速排序的最坏空间复杂度为 O ( n ) O(n) O(n)；
快速排序的最好空间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2​n)；
快速排序的平均空间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2​n)；

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.