测试开发人员需了解的基础算法系列（一）

背景介绍

算法 这个近两年由于大数据人工智能的兴起而被提及最多的关键词之一，从而在IT这个猿类圈中有了基因变异-算法工程师，被其他老猿类羡慕嫉妒恨，其实我觉得也没必要去羡慕，做好我们自己在本职的岗位做到优秀也不会比别人差的，有的测试猿说测试不需要了解或者研究算法，根本没毛线用，原来我也是这么认为，不过随着时间的推移猿类世界的基因突变，越来越发现不了解不懂算法会越来越没有竞争力，不为别的为了升职加薪你也得学啊，当然在测试过程中也更有助于我们了解需求，比如我们的项目就用到了一致性哈希算法，以及广度优先图的概念，二分查找等所以是有很大必要的。测试猿们，我们可以不需要每个算法都精通熟悉，但是基础的我们还是要必须知道地，以下就对这些常见的基础的一些算法做一些个人的总结与理解，有不对的地方还请各位大神指正！

二分查找

假设在电话本虽然我们都不用电话本了中查找以我博客名allen的首字母A开头的人很容易第一次就能查到所有以A开头的人，那么假如是K呢你可能想到直接从中间找啊，还有假如要登陆CSDN，csdn必须要检查你是否拥有其网站的账户，假如你的名字也是K开头网站要从A开始查找，其实更科学的方式是从中间开始，所以基于以上情况都可以使用同一算法解决此问题，这种算法就是二分查找

举个栗子

假如要从1-100中随便猜一个数字，你每次猜后我都会说大或者小了，假设你从1开始猜，过程大概就是假如你要猜的是100那么很不幸你要猜99次，当然单反有点脑子的肯定都是随机猜，当然还有更佳的方式，那就是从50开始。过程如下。

1,2,3,4,5，6,7,8,9。。。。。。。。。100
- 50 小了 但是排除了一半的数字
- 75 大了 余下的数字又减少了一半
- 。。。。。
- 每次都从剩下的数字排除了一半

每次猜排除数字的个数如下
100个元素–>50–>25–>13–7–4–2–1(对了)
所以不论猜的是什么，在7次之内都能猜到，每次都能排除一半的假答案
所以
对于二分查找，对于包含n个元素的列表用二分查找最多可以需要log^n步(对坐Log 以2为低n 的对数)
下面让我们来实现二分查找,下面是一个猜数字的游戏，每一次我们都从中间猜起，以一个List为例子，如果猜中就返回其位置，设定两个边界值
- low = 0
- high = len(list)-1
每次都从中间猜起是：mid = (low+high) / 2 如果mid不是整数，python会自动向下取整guess = list[mid]
完整代码如下

#list为传入的猜的列表，onj_num 为目标数
def guess_num(list,obj_num):
    low = 0
    high = len(list) -1
    while low <= high: #只要范围没有缩小的只包含一个元素就检查中间的元素
        mid = (low + high)/2
        guess = list[mid]
        if guess == obj_num: #找到了元素
            return mid
        if guess > obj_num: # 猜的数字大了
            high = mid -1
        else: #猜的数字小了
            low = mid +1
    return None #猜的数字不在列表中
my_list = [1,3,5,8,111]
print guess_num(my_list,3) --->1 第一个位置
print guess_num(my_list,2222)---->None 没有找到元素2222

快速排序

我们队一个数组进行快速排序，对排序来说最简单的数组是什么样的嘛，那就是根本不需要排序的数组
- [ ] 空数组
- [20] 只有一个元素的数组
因此只要我们找到它的基线条件：空数组或者只有一个数组，这种情况就直接返回数组本身不需要排序,如下所示：

    def quicksort(array):
    if len(array) ==0 or len(array) == 1:
        return array 

那么假如3个元素，甚至更多元素的数组排序怎么办呢，其实一样的那就是想办法找到它的基线条件，下面介绍一下快速排序的原理,首先从数组中选择一个元素，作为基准值，接下来找出比基准值小的和大的如下假如以第一个元素15作为基准值
- 例子list=[15.10.33.85,8]
- 比15小的放到一个数组里[10,8]
- 比15大的放到一个数组里[33,85]
- 同理在[10,8]中以10作为基准值把比10小的放到[8],比10大的为[ ]空数组
- 同理在[33,85]中以33作为基准值把比33小的放到[ ]空数组,比33大的为[85 ]空数组
以上后续发现都用了递归的方式排序方式都是一样的，所以转化成代码就是如下：

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        jizhun_num = array[0]#极限条件
        less = [i for i in array[1:] if i <= jizhun_num]#小于基准值的
        big =  [i for i in array[1:] if i > jizhun_num]#大于基准值的
        return quicksort[less] + [jizhun_num] + quicksort[big]
print quicksort([10,3,5,11,8])

总结

以上两个是比较常见和基础的排序算法之一，做一个抛砖引玉，希望可以提高一下测试人员对算法的兴趣，在这里推荐一本算法入门书籍《算法图解》如下，通俗易懂有趣