基础算法

二分查找

def bin_search(items, key):
  """二分查找"""
    lindex = 0
    rindex = len(items) - 1
    while True:
        index = int((lindex + rindex)/2)
        if key = items[index]:
            rindex = index - 1
        elif key > items[index]:
            lindex = index + 1
        else:
            return index
    return -1

冒泡排序(优化)

# *前面的是位置参数 - 传参时只需要参数值对号入座即可
# *后面的时命名关键字参数 - 传参是必须书写为"参数名=参数值"格式
# 好的函数应该是没有副作用的(调用函数不会让函数的调用者收到任何影响)
def bubble_sort(origin_items, * comp = lambda x, y: x > y):
    """冒泡排序 - 平方复杂度 - O(N**2)"""
    items = origin_items[:] # 此处优化算法不对原始数据造成影响
    for i in range(1, len(items),):
        swapped = False
        for j in range(0, len(items)-i):
            if comp(items[j], items[j+1]): # 此处解耦比较运算符, 扩大函数适用范围
                items[j], items[j+1] = items[j+1], items[j]
                swapped = True

       # 此处优化为双向排序, 经过此优化后的冒泡排序算法又称为搅拌排序、鸡尾酒排序等
       for j in range(len(items) - i, 0, -1):
             if comp(items[j-1], items[j]):
                 items[j], items[j-1] = items[j-1], items[j]
                 swapped = True
        if not swapped: # 如果某一轮比较全程没有发生交换则终止循环
            break
    return items

归并排序

def merge(items1, items2, comp):
    """有序列表合并"""
    items = []
    index1, index2 = 0, 0
    while index1 < len(items1) and idx2 < len(items):
        if comp(items[index1], items2[index2]):
            items.append(items1[index1]
            index1 += 1
        else:
            items.append(items2[index2])
            index2 += 1
    items += items1[index1:]
    items += items2[index2:]
    return items


# 函数的递归调用 - 一个函数如果直接或者简介的调用了自身就成为递归调用
# 写递归调用的函数又两个关键点:
# 1. 收敛条件 - 什么时候可以停止递归
# 2. 递归公式 - 下一轮的调用跟当前轮次的关系
def merge_sort(items, comp=lambda x, y: x <= y):
    """归并排序"""
    if len(items) < 2:
        return items[:]
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right, comp)

动态规划算法

# 斐波拉契数列: 1 1 2 3 5 8 13 21 34 55
def fib(num):
    """斐波拉契数列 - O(2**N)"""
    if num in (1, 2):
        return 1
    return fib(num - 1) + fib(num - 2)


# 斐波拉契优化
# 动态规划
def fib(num, temp={}):
    """斐波拉契数列"""
    if num in (1, 2):
        return 1
    try:
        return temp[num]
    except KeyError:
        temp[num] = fib(num - 1) + fib(num -2)
        retuurn temp[num]