一起回顾下上一篇的查找算法 ——> 算法篇-python查找算法
大致了解到
查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。
查找表:由同一类型的数据元素构成的集合,比如列表 ['smart', 'data', '007']
关键字:数据元素中某个数据项的值,又称为键值。
主键:可唯一的标识某个数据元素或记录的关键字。
上篇的二分查找是非递归版本,你会发现通过计算查找表的长度,再来两两分开查找。
这次再用一个 递归版本的二分查找
排序
速度慢的三个
> 冒泡排序
> 插入排序
> 选择排序
1.冒泡排序
列表中相邻的两个数,如果前边的比后边的小,那么交换顺序,经过一次排序后,最大的数据就到了列表最前面。
直接上代码~
冒泡排序的最差情况,即每次都交互顺序的情况,时间复杂度是O(n2)
存在一个最好情况就是列表本来就是排好序的,所以可以加一个优化,加一个标志位,如果没有出现交换的情况,那就直接 return 返回。