算法

二分查找

引入

假设要在电话簿中找一个名字以K打头的人， 可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。

这是一个查找问题，可以用二分查找的思想来解决

算法思想

二分查找的前提一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。算法时间复杂度为${\log }_{2}n$,与简单查找相比，当需要搜索的元素越多时，二分查找比简单查找越快。

代码实现

def binary_search(list,item):
    low = 0 
    high = len(list) - 1
    while(low <= high):
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item: 
            return True
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None
my_list = [1,3,5,7,9]
print (binary_search(my_list,3))
print (binary_search(my_list,0))

大O表示法

大O表示法计算的是操作数，指出了算法有多快，即算法运行时间的增速。例如，假设列表包含n个元素。简 单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法， 这个运行时间为$O(n)$。

常见的大O表示法的运行时间如图所示：

选择排序

引入

假设你的计算机存储了很多乐曲。对于每个乐队，你都记录了其作品被播放的次数。你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。该如何做呢？

这是一个排序问题，在这里我们选用选择排序的思想来解决这个问题。解决方法如下：

• 遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。
• 再次这样做，找出播放次数第二多的乐队。继续这样做，你将得到一个有序列表。

算法思想

选择排序是一种简单直观的排序算法，首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。算法时间复杂度为$O(n^2)$

代码实现

#找到最小值
def findsmallest(arr):
    smallest = arr[0]
    smalleset_index = 0
    for i in range(1,len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smalleset_index = i
    return smalleset_index
#选择排序
def selectionsort(arr):
    NewArr = []
    for i in range(len(arr)):
        smallest = findsmallest(arr)
        NewArr.append(arr.pop(smallest))
    return NewArr
print (selectionsort([8,5,9,2]))

递归算法

引入

假设你在祖母的阁楼中翻箱倒柜，发现了一个上锁的神秘手提箱。祖母告诉你，钥匙很可能在下面这个盒子里。这个盒子里有盒子，而盒子里的盒子又有盒子。钥匙就在某个盒子中。为找到钥匙，你将使用什么方法？

我们可以将这个问题类比成俄罗斯套娃，打开的每一个盒子里的内容不同，但打开盒子这个动作却一直在不断重复,利用这个思想我们可以得到解决问题的方法是：

1. 检查盒子中的每样东西。
2. 如果是盒子，就回到第一步。
3. 如果是钥匙，就大功告成！

算法思想

递归算法只是让解决方案更清晰，并没有性能上的优势。编写递归函数时，必须告诉它何时停止递归。正因为如此,每个递归函数都有两部分：基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

代码实现

问题：利用递归的方法求3！

def factorial(i):
    sum=0 
    if i==0:#0的阶乘
        sum=1 
    else:
        sum=i*factorial(i-1)
    return sum
print(factorial(3))

栈

引入

假设你去野外烧烤，并为此创建了一个待办事项清单———叠便条。因为是一叠便条，故我们将插入的待办事项放在清单的最前面；读取待办事项时，只读取最上面的那个，并将其删除。因此这个待办事项清单就只有两种操作：压入 （插入）和弹出（删除并读取）。我们该如何使用这堆便条呢？

这种数据结构称为栈。栈是一种简单的数据结构，它只允许在一端进行插入或删除操作。解决问题的方法是：

算法思想

我们沿用上一节递归实现3！的例子，你还记得如何用代码实现它吗？

def fact(x):
    sum=0 
    if x==1:#0的阶乘
        sum=1 
    else:
        sum=x*fact(x-1)
    return sum
print(fact(3))

下面来详细分析一下调用fact(3)时调用栈是如何变化的

快速排序