Python三种经典算法分享：查找、排序、递归。

本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理

本文章来自腾讯云 作者：企鹅号小编

私信小编回复01可领取学习资料以及学习视频

iTesting，爱测试，爱分享

沉寂了一段时间，继续学习。

算法这个系列我想分享很久了，奈何本身对算法不是特别了解，又找不到合适的载体来分享。

最近看了本有趣的算法书， 文中通过图文并茂的讲解给我很大启发，尝试着分享下。需要注意的是， 文中各个算法的写法不是简单的拷贝，算理解思想后拿Python3重新写了遍，分享的代码和书中的例子也稍有不同，加了些日常工作中会做的处理，如有不适，请联系我。

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

对于包含N个元素的列表，用二分查找最多需要log2 N 步。（对数是幂运算的逆运算）

大O表示法指出了算法有多快。例如，假设列表包含n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作。使用大O表示法，这个运行时间为O (n )。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速 。

再来看一个例子。为检查长度为n 的列表，二分查找需要执行log n 次操作。使用大O表示法，这个运行时间怎么表示呢？O (log n )。一般而言，大O表示法按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

在这里插入图片描述

选择排序

思想：

找出数组中最小的元素

把数组中最小的元素pop出来到新的数组里。

重复以上操作直到原数组为空

在这里插入图片描述

需要存储多个元素时，可使用数组或链表。

数组的元素都在一起。

链表的元素是分开的，其中每个元素都存储了下一个元素的地址。

数组的读取速度很快。

链表的插入和删除速度很快。

在同一个数组中，所有元素的类型都必须相同（都为int、double等）

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

最小公倍数：

思想：

两个数(x, y)的最小公倍数数的算法为：两个数相乘再除以他们的最大公约数

0没有公倍数

在这里插入图片描述

公约数，公倍数，适用于自然数。

快速排序

思想：

少于2个元素的数组不需要排序

找一个元素作为基数

小于基数的放一个数组

大于基数的放一个数组

针对小于基数的数组做快速排序，暂且叫low

针对大于基数的数组做快速排序, 暂且叫high

最终排序后的 low + 【基数】+ high，就是排好序的数组

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