Python教程

【排序算法】快速排序及其C语言实现_Python实现

本文主要是介绍【排序算法】快速排序及其C语言实现_Python实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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


快速排序

    • 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.

这篇关于【排序算法】快速排序及其C语言实现_Python实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!