系列文章目录
第一章:二分查找及大O表示法
第二章:选择排序
第三章:递归和快速排序
文章目录
- 系列文章目录
- 前言
- 一、递归
- 1、基线条件和递归条件
- 2、递归练习
- 二、快速排序
- 三、总结
前言
积累算法,记录学习
一、递归
程序中的递归实现简单来说就是函数调用自己
使用循环会使程序更加高效,但使用递归会使程序更易被理解。
但是递归使用时候要注意一点,即停止条件,否则会使你的程序陷入无限循环中。
1、基线条件和递归条件
增加这两个条件的原因就是为了防止程序自己无限循环下去。比如:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18>>> def countdown(i): print(i) countdown(i-1) >>> countdown(5) 5 4 3 2 1 0 -1 -2 -3 -4 ......
但是我们加上这两个条件:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16>>> def countdown(i): print(i) if i <= 0: # 基线条件 return else: # 递归条件 countdown(i-1) >>> countdown(5) 5 4 3 2 1 0
因此递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。
2、递归练习
编写一个递归函数,计算列表中包含的元素数:
复制代码
1
2
3
4
5
6>>> def lenlist(arr): if arr: return 1 + lenlist(arr[1:]) else: return 0
编写求和函数,能求出列表中所有值的加和:
复制代码
1
2
3
4
5
6>>> def sum1(arr): if arr: return arr[0] + sum1(arr[1:]) else: return 0
二、快速排序
快速排序是一种常用的排序算法,比选择排序快得多。例如, C语言标准库中的函数qsort()实现的就是快速排序。
快速排序思路也用到了递归,其算法思路是:
- 首先判断列表长度,当列表为空或者只有一个数值时就不需要比较,这就是基线条件
- 选择一个基准值(pivot),用这个基准值去将列表分成两部分:[小于基准值的部分],[大于基准值的部分],这样的 “ 粗排序 ” 就能将原本的列表变成:[小于基准值的部分] + [pivot] + [大于基准值的部分]
- 将上面步骤分成的两部分再一次当作输入参数,实现递归。
程序实现如下:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13>>> def qsort(array): if len(array)<2: return array else: pivot = array[0] less = [i for i in array[1:] if i <= pivot] greater = [i for i in array[1:] if i > pivot] return qsort(less) + [pivot] + qsort(greater) >>> qsort([10,5,3,4]) [3, 4, 5, 10]
快速排序的程序速度用大O表示法是nlogn
引用《图解算法》中的一个图:
因此在较大规模数据上,快速排序还是很优美的。
三、总结
- 递归(D&C)将问题逐步分解。使用D&C处理列表时,基线条件很可能是空数组或只包含一个元素的数组
- 实现快速排序时,请随机选择用作基准值的元素。快速排序的平均运行时间时O(nlogn)
- 大O表示法的常量有时候事关重大,这就是快速排序比合并排序快的原因
- 比较简单查找和二分查找时,常量几乎无关紧要,因为列表很长时,O(logn)比O(n)快得多。
最后
以上就是落后烧鹅最近收集整理的关于算法学习(三)—— 递归和快速排序系列文章目录前言一、递归二、快速排序三、总结的全部内容,更多相关算法学习(三)——内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复