Python算法分享系列-查找，排序，递归

iTesting，爱测试，爱分享

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

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

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

二分查找 --仅当列表是有序的时候才能用

思想：

1.目标是找数组中的某一个元素，暂叫item

2.找出整个数组中间的那个元素，它下标mid，数组被它一分为二

3.比较下标mid对应的元素和item，如果mid对应的元素大，查找范围缩小到mid前面的那一半数组，反之，缩小到mid后的那一半数组

4.重复3，直到item==mid

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

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

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

O (log n )，也叫对数时间 ，这样的算法包括二分查找。

O (n )，也叫线性时间 ，这样的算法包括简单查找。

O (n * log n )，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。

O (n 2 )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。

O (n !)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

大O表示法指出了最糟情况下的运行时间.

选择排序

思想：

找出数组中最小的元素

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

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

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

数组的元素都在一起。

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

数组的读取速度很快。

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

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

数字和链表区别：

数组： 连续空间， 预留空间， 查找方便， 插入麻烦，必须移动后面的所有元素，如果没有空间，必须将数组复制到其他地方。

链表： 分散空间，查找麻烦，插入方便，只需移动前面元素指向的地址。

数组链表

读取O（1）O（n）

插入O（n）O（1）

删除O（n）O(1)

访问顺序访问随机访问

O(n)=线性时间

O(1)=常量时间

递归

每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

deffact(x):

ifx

return1

else:

fact(x-1) #---递归条件

print(fact(6))

我们拿最大公约数来举例：

思想：

假定x > y（如果x < y，则互换）

求x对y的余数，假定余数为z

求y与z的最大公约数即为x，与y的最大公约数

0没有公约数

最小公倍数：

思想：

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

0没有公倍数

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

快速排序

思想：

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

找一个元素作为基数

小于基数的放一个数组

大于基数的放一个数组

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

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

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

总结下：

D&C算法（divided and conqure）是递归的。使用D&C解决问题的过程包括两个步骤。

(1) 找出基线条件，这种条件必须尽可能简单。

(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。

散列表（Hash Table）

散列函数：

散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。

散列函数总是将同样的输入映射到相同的索引。例如你每次输入iTesting，它返回你的总是同一个数字。

散列函数将不同的输入映射到不同的索引。比如iTesting对应6， python对于0.如果散列函数将不同的键映射到同一个位置，就在这个位置存储一个链表。

散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会返回无效索引100。

结合使用散列函数和数组创建了一种被称为散列表 （hash table）的数据结构。

不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的散列表实现为字典 ，你可使用函数dict 来创建散列表。

散列表被用于大海捞针式的查找，散列表适合用于：

模拟映射关系；

防止重复；

缓存/记住数据，以免服务器再通过处理来生成它们。

总结：

你可以结合散列函数和数组来创建散列表。

冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。

散列表的查找、插入和删除速度都非常快。

散列表适合用于模拟映射关系。

一旦填装因子超过0.7，就该调整散列表的长度（通常将数组长度加倍）。

散列表可用于缓存数据（例如，在Web服务器上）。

散列表非常适合用于防止重复。

（填装因子是数组中被占用的位置，例如大小为3的数字，有2个被占用，则填装因子为2/3）

惯例放赞赏码：）

END

关注iTesting