【排序算法】快速排序及其C语言实现_随笔

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

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

快速排序

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

void quick_sort(int arr[], int low, int high)
{
	if(low=pivot) high--;
		arr[low]=arr[high];
		while(low 
运行结果：
 
 
     
      
       
        
         图
        
        
         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.					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5721506.html

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

发表评论

评论列表（0条）