算法图解阅读笔记——第二曲（递归和快速排序）

骑猪看日落 2021-05-12 11:50 354阅读 0赞

#### 目录结构 ####

第3章 递归

第4章 快速排序

--------------------

#### 正文 ####

## 递归 ##

### 什么是递归（毕竟自己调用自己这样的解释太抽象了） ###

*  先以书中的例子介绍递归，然后用自己的理解来描述递归

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]

*  上述是一个盒子嵌套这一个盒子的问题，类似套娃，找钥匙的过程有两种方法：**第一可以使用for循环**，**第二也可用递归**。（那两者有什么区别呢？）
    
     *  假设现在我们的盒子总共是有三层嵌套，钥匙在第三层，编号为⑤的盒子中（如下图）
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]
    
    1.  使用 for 循环寻找钥匙是逐层查找，也就是说先找第一层，接着第二层、第三层，那么最后的查找盒子的顺序便是①②③④⑤⑥，当然我们在第⑤个盒子中找到了钥匙，也就不需要再找第⑥个盒子了。
    2.  使用递归寻找钥匙是按盒子查找，一个盒子走到黑，那么递归的查找顺序便是①②④⑤③⑥，同理，在第⑤个盒子中找到钥匙后，就不需要再找第③和第⑥个盒子了。
    
    选用循环或者递归套用原文一句话：**“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”**

### 递归两条件（基线条件和递归条件） ###

*  基线条件：指的是函数不再调用自己，从而避免无限循环
 *  递归条件：指的是函数调用自己
 *  注意：**实现递归时，要时刻关注以上两个条件**

### 调用栈 ###

*  栈这种数据结构只有两种操作：**压入(push)和弹出(pop)**
 *  在调用函数时计算机会为每个函数块分配一块内存，并压入调用栈中，当调用完毕后，再将该内存块从调用栈中弹出。
 *  注意：如果调用栈很高（长），就意味这存储了大量的函数调用信息，将占用大量的计算机内存。所以在递归时，没控制好基线条件，发生无限循环时，很可能导致内存溢出。

## 快速排序 ##

### 分而治之（D&C) ###

*  是一种著名的递归式问题的解决方法
 *  步骤：
    
    1.  找出基线条件，这种条件必须尽可能简单。
    2.  不断将问题分解（或者说缩小规模），直到符合基线条件为止。

### 快速排序 ###

*  快速排序也是一种排序算法，比选择排序快的多，采用了分而治之的方法。

**实现快速排序**

假如我们需要排序\[0, 3, 1\]这样的数组，根据步骤：先找基线条件—当数组中没有元素或者只有一个元素时，就不需要继续排序了；再将问题缩小规模—找一个基准值将原列表根据基准值分为两派（比基准值大的和比基准值小的），然后再每一派中继续使用递归条件，这样问题规模就越来越小了，直到符合基线条件为止。

def quick_sort(alist):
        if len(alist) < 2:      # 基线条件
            return alist
        else:                   # 递归条件
            pivot = alist[0]  # 基准值
            small = [item for item in alist[1:] if item <= pivot]
            large = [item for item in alist[1:] if item > pivot]
    
            return quick_sort(small) + [pivot] + quick_sort(large)
    
    print(quick_sort([0, 3, 1]))
    
    # Out
    # [0, 1, 3]
    # print(quick_sort([1]))

### 大O表示法 ###

常见大O运行时间

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]

*  如果两种算法的大O运行时间相同，这时候常量就显得十分重要了，这就是快速排序比合并排序快的原因所在；如果两种算法的大O运行时间不同，这时候常量将无关紧要。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210511/1d23bc4493ce403b9459f3915b6ddac6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210511/bf2dda732d824dac9ff1a3875fd004fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210511/269d22b84b2d49629f2d68d36f1d977e.png