数据结构与算法 | 快速排序前言1 什么叫快速排序？2 代码实现3 时间复杂度4 算法稳定性5 补充参考

63 阅读 0 评论 42 点赞

我是靠谱客的博主爱撒娇咖啡，最近开发中收集的这篇文章主要介绍数据结构与算法 | 快速排序前言1 什么叫快速排序？2 代码实现3 时间复杂度4 算法稳定性5 补充参考，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快速排序

前言
1 什么叫快速排序？
2 代码实现
3 时间复杂度
4 算法稳定性
5 补充
参考

前言

“手写快排” 是面试中算法题出现频率很高的一个题目，所以一定得掌握了~接下来我们就一起看看啥叫快速排序？又该如何去用Python手写快速排序呢？

1 什么叫快速排序？

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort）
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤：

选基准。从数列中挑出一个元素，称为"基准"（pivot），
设置两个游标，进行分区操作。重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归排序。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

图解：
在这里插入图片描述

2 代码实现

思路：

定义一个初始值mid_value 和两个游标 low high
控制两个游标的移动，要实现的效果是什么呢？就是最后让mid_value左边的值都比它小，右边的值都比它大！这样分成两部分之后再递归调用这个函数就ok了！能实现最终的排序！
那我们要怎么操作呢？【两边夹逼！】
注意：如何实现递归呢？如果对list进行切片，不太好处理，还是希望能够在原始的list直接操作，所以可以在list传参之后，还传入两个参数，即要处理的元素的首尾两个位置即可！

def quick_sort(alist, first, last):
    
    '''
    function: 实现快速排序
    parameters:
    - alist:待排序list
    - first:待排序list的首位置
    - last:待排序list的末位置
    '''
    
    if first >= last:
        return # 返回空
    # 下面的代码需要执行 有一个终止条件 即 first>=last
    
    # 实现快速排序
    # 首先定义两个游标
    low = first
    high = last
    # 定义初始中值
    mid_value = alist[first]
    
    # 开始逐个判断进行游标移动+元素位置互换

    while low < high :
        while alist[high] >= mid_value and high > low:
            high -= 1
        # 跳出循环 表明此时high指向的值小于mid_value 需要交换
        alist[low] = alist[high]

        # 开始移动low游标
        while alist[low] < mid_value and high > low:
            low += 1
        # 跳出循环 表明此时low指向的值大于mid_value 需要交换
        alist[high] = alist[low]

        # 上面两步结束需要一个终止条件：即两个游标重合则停止！
    
    # 跳出循环 表明两个游标重叠了！此时再交换值
    alist[low] = mid_value
    
    
    # 递归实现 low表示此时为两个游标重叠的位置！根据这个位置一分为2 对每个子list进行递归排序
    quick_sort(alist, first, low-1) # 左分区排序
    quick_sort(alist, low+1, last) # 右分区排序

alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist, 0, len(alist)-1)
alist

[17, 20, 26, 31, 44, 54, 55, 77, 93]

3 时间复杂度

时间复杂度：

最优时间复杂度： $n O (l o g n)$ 。因为每次一分为2 最终分多少次样本量达到n呢？故为对数复杂度！同时一开始先要遍历一遍样本！所以要乘以 $n$
最坏时间复杂度： $O(n^2)$ 。list本身是有序的！这样每次分区后都只需要重排右边的分区，但需要进行n轮，每次遍历所有样本，时间复杂度退化为平方复杂度！没有实现真正的二分。