算法

递归

递归有两大特性：

　　1.自己调用自己。

　　2.有结束条件。

　　满足了以上两点的函数就是递归函数。

实例1：

def func(x):
    if x > 0:
        print(x)
        func(x - 1)


func(3)  # 3,2,1

图解：

 实例2：

def func1(x):
    if x > 0:
        func1(x - 1)
        print(x)


func1(3)  # 1,2,3

图解：

实例3：

 一段有n个台阶组成的楼梯，小明从楼梯的最底层向最高处前进，它可以选择一次迈一级台阶或者一次迈两级台阶。
 问：他有多少种不同的走法？
 分析：

# 如果最后一步走一个台阶，一共有f(n-1)中走法
# 如果最后一步走两个台阶，一共有f(n-2)中走法
# 由此推出f(n)=f(n-1)+f(n-2)

代码实现：

 def t1(n):
     if n==1:
         return 1
     elif n==2:
         return 2
     return t1(n-1)+t1(n-2)

如果可以走三个台阶

 def t2(n):
     if n == 1:
         return 1
     elif n == 2:
         return 2
     elif n == 3:
         return 4
     return t2(n - 1) + t2(n - 2) + t2(n - 3)

铺砖：
有一块长度为N米，宽度为1米的地需要铺砖，现在有两种规则的砖可以使用，1*1,1*2,一共有多少种铺法。和上面解决方法一样

汉诺塔问题
问题背景：

有三个柱子，在一根柱子上从下往上按照大小顺序摞着N片黄金圆盘，
把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

解题思路：

n个盘子时：
1.把n-1个圆盘从A经过C移动到B
2.把第n个圆盘从A移动到C
3.把n-1个小圆盘从B经过A移动到C

代码实现：（递归）

def hnt(n, A, B, C):  # 将n个圆盘从A经过B移动到C。
    if n > 0:
        hnt(n - 1, A, C, B)  # 将n-1个圆盘从A经过C移动到B。
        print("从%s移动到%s" % (A, C))
        hnt(n - 1, B, A, C)  # 将n-1个圆盘从B经过A移动到C。


hnt(3, "A", "B", "C")

汉诺塔移动次数的递推式：h(x)=2h(x-1)+1，x是圆盘个数
斐波那锲数列

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,.......
这个数列从第3项开始，每一项都等于前两项之和。

递归实现

def fib(n):  # 默认从0开始
    if n==0 or n==1:
        return 1
    return fib(n-1)+fib(n-2)

print(fib(5))

字典实现

def fib(n):
    l=[1,1]
    if n == 0 or n == 1:
        return 1
    for i in range(2,n+1):
        l.append(l[-1]+l[-2])
    return l[-1]

print(fib(1))

通过赋值实现

def fib(n):
    if n == 0 or n == 1:
        return 1

    a = 3  # a刚开始赋的第一个值可以使任意数字，为了占据一个位置，方便后续变量向前赋值
    b = 1
    c = 1
    for i in range(2, n + 1):
        a = b
        b = c
        c = a + b
    return c


print(fib(5))

# 以上的核心思想都是递归 func(n)=func(n-1)+func(n-2)

 二分查找

循环实现

def bin_search(l, val):
    low = 0  # low和high,mid指的是索引
    high = len(l) - 1
    while high >= low:
        mid = (low + high) // 2  # 整除2
        if l[mid] > val:
            high = mid - 1
        elif l[mid] < val:
            low = mid + 1
        else:
            return l[mid]
    return "列表%s中没有%s这个值" % (l, val)


l = [1, 2, 3, 4, 5, 6]
print(bin_search(l, 5))

 递归实现，效果不好

def bin_search_rec(data_set, value, low, high):
    if low <= high:
        mid = (low + high) // 2
        if data_set[mid] == value:
            return data_set[mid]
        elif data_set[mid] > value:
            return bin_search_rec(data_set, value, low,mid - 1)
        else:
            return bin_search_rec(data_set, value, mid + 1, high)
    else:
        return "列表%s中没有%s这个值" % (l, value)

l = [1, 2, 3, 4, 5, 6]
print(bin_search_rec(l,9,0,4))

排序LB三人组：

# 时间复杂度：O(n2)
# 空间复杂度：O(1)

检测性能的导入部分

import random
from test_time import cal_time

检测时间装饰器

import time


def cal_time(func):
    def inner(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print("%s running time:%s秒" % (func.__name__, t2 - t1))
        return result

    return inner

冒泡排序

# 简单冒泡
# 思路
#列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数代码关键点：分清有序区和无序区
@cal_time
def bubble_sort(li):
    for i in range(len(li) - 1):  # i 表示第i次冒泡
        for j in range(len(li) - i - 1):  # j 表示索引位置
            if li[j] > li[j + 1]:  # 如果前面的值比后面大，那么这两个数换个位置
                li[j], li[j + 1] = li[j + 1], li[j]

# 优化冒泡
@cal_time
def bubble_sort_2(li):
    for i in range(len(li) - 1):  # i 表示第i次冒泡
        exchange = False
        for j in range(len(li) - i - 1):  # j 表示索引位置
            if li[j] > li[j + 1]:  # 如果前面的值比后面大，那么这两个数换个位置
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        # 如果某一次冒泡期间没有元素互换位置，说明后面的元素已经是有序的了，可以直接返回
        if not exchange:
            return   

插入排序
思路

# 列表被分为有序区和无序区两个部分。最初有序区只有一个元素。每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
# 代码关键点：摸到的牌，手里的牌
# 何时插入?
    1.j 位置的值小于tmp
    2.j=-1 此时tmp的值在当前的有序区里是个极限值
    li[j+1]=tmp 

代码实现

@cal_time
def insert_sort(li):
    for i in range(1, len(li)):
        j = i - 1  # i 为要插入数的索引，j 为要插入的位置
        tmp = li[i]
        while j >= 0 and li[j] > tmp:  # 1,2 的反向条件成立，循环继续
            li[j + 1] = li[j]  # j位置的值向右移动一个位置
            j -= 1  # 要插入的位置向前移动一个
        li[j + 1] = tmp  # 不管条件1还是条件2成立，都是讲tmp插入到j+1的位置

选择排序
思路

# 一趟遍历记录最小的数，放到第一个位置；再一趟遍历记录剩余列表中最小的数，继续放置；
……

# 代码关键点：无序区
最小数的位置

代码实现

# 找到无序区最小的数，放到最前面，变成有序区第一个数
def find_min(li):
    min_val = li[0]  # 默认第一个数为最小的数
    for i in range(1, len(li)):  # 排除第一个数，所以循环从索引1开始
        if li[i] < min_val:
            min_val = li[i]
    return min_val

# 找到无序区最小的数的位置
def find_min_pos(li):
    min_pos = 0  # 默认第一个数为最小的数的位置
    for j in range(1, len(li)):
        if li[j] < li[min_pos]:
            min_pos = j
    return min_pos

# 进行排序
@cal_time
def select_sort(li):
    for i in range(len(li) - 1):  # 最后一个数肯定是个极限值，不用选择，循环len(li)-1次即可
        # 无序区的范围[i,len(li)]  i 循环第i次
        min_pos = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_pos]:
                min_pos = j  # 将j的位置赋值给min_pos
        li[i], li[min_pos] = li[min_pos], li[i]

检测性能打印部分：

li = list(range(1000))
random.shuffle(li)  # 打乱顺序
bubble_sort(li)
bubble_sort_2(li)
insert_sort(li)
select_sort(li)
# print(li)

 排序NB三人组

检测性能导入部分

import sys
import random
from test_time import cal_time

sys.setrecursionlimit(1000)

快排
思路

# 取一个元素p（第一个元素），使元素p归位；
# 列表被p分成两部分，左边都比p小，右边都比p大；
递归完成排序。

# 代码关键点：整理，递归

第一部分：整理

def quick_sort(li,left,right):  # 第一部分整理
    if left<right:  # 确保至少两个元素
        mid=partition(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)

测试时间的函数（可以不写）

# 加上装饰器，检测时间，里面有递归，函数结构要改变
 def _quick_sort(li, left, right):
     if left < right: # 至少两个元素
         mid = partition(li, left, right)
         _quick_sort(li, left, mid-1)
         _quick_sort(li, mid+1, right)


 @cal_time
 def quick_sort(li):
     _quick_sort(li, 0, len(li)-1)

第二部分：递归

def partition(li, left, right):  # 递归

    # 下面两行代码是优化用的，可以减少最坏情况出现的概率
    # 最坏情况，我们排序的结果和给的数据完全相反
    i = random.randint(left, right)
    li[left], li[i] = li[i], li[left]

    tmp = li[left]
    while left < right:
        # 目前是从小到大排序，从大到小的话，只需要将下面的两个>=,<=换个位置即可
        while left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    # 无论从哪边结束，赋值操作都是一样的，此时li[left]和li[right],写那个都一样
    li[left] = tmp
    return left

打印测试时间

#系统排序（可以不写）
@cal_time
def sys_sort(li):
     li.sort()

li = list(range(100000, -1, -1))
random.shuffle(li)
quick_sort(li, 0, len(li)-1) # 不写装饰器时时函数的调用
quick_sort(li) # 写装饰器时函数的调用

# print(li)

堆排
树与二叉树简介

# 树是一种数据结构          比如：目录结构
树是一种可以递归定义的数据结构
树是由n个节点组成的集合：
如果n=0，那这是一棵空树；
如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。
# 一些概念
根节点、叶子节点
树的深度（高度）
树的度
孩子节点/父节点
子树

特殊且常用的树——二叉树

 　二叉树：度不超过2的树（节点最多有两个叉）

两种特殊二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

二叉树的存储方式

# 链式存储方式
# 顺序存储方式（列表）

# 父节点和左孩子节点的编号下标有什么关系？
0-1 1-3 2-5 3-7 4-9
i=2i+1

# 父节点和右孩子节点的编号下标有什么关系？
0-2 1-4 2-6 3-8 4-10
i=2i+2
# 父节点和子节点的编号下标的对应关系：i=(子节点下标-1)//2

 堆前传小结

树二叉树完全二叉树

二叉树是度不超过2的树
满二叉树与完全二叉树
（完全）二叉树可以用列表来存储，通过规律可以从父亲找到孩子或从孩子找到父亲。

堆排序

堆
大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小

                  

堆的向下调整性质

假设：节点的左右子树都是堆，但自身不是堆

 当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆

堆排序过程

建立堆
得到堆顶元素，为最大元素
去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。
堆顶元素为第二大元素。
重复步骤3，直到堆变空

堆排序代码

# 堆排（核心：调整)
def sift(li, low, high):
    # low 表示根位置    high 表示最后元素的位置
    tmp = li[low]
    i = low # i指向空位
    j = 2 * i + 1 # j指向孩子
    # 把tmp写回来有两种条件 1. tmp > li[j]  2. j位置没有值 （也就是i已经是叶子了）
    while j <= high:    # 对应退出条件2
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在且右孩子更大
            j += 1  # j指向更大的孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:       # 对应退出条件1
            break
    li[i] = tmp # 不管哪个条件退出，i这个位置都是空位，将根位置的值赋值给i

@cal_time
def heap_sort(li):
    n = len(li)
    # 1. 建立堆  low在不断变化
    for low in range(n//2-1, -1, -1):  # n//2-1-->n-1-1//2
        sift(li, low, n-1)  # low表示每个小堆的堆顶，n-1表示堆的最后一个元素的下标
    # print(li)

    # 2. 挨个出数 退休-棋子-调整
    # high在不断变化，0号位置不停的和high位置在做交换
    for high in range(n-1, -1, -1):
        li[0], li[high] = li[high], li[0]
        sift(li, 0, high-1) # 每调整一次，元素个数就少1
        # print(li)


li = list(range(100000))
random.shuffle(li)
heap_sort(li)
print(li)

内置堆

import heapq

li = [2,5,7,8,9,6,1,4,3]
heapq.heapify(li)
print(li)
heapq.heappush(li, 0)
print(li)
print(heapq.heappop(li))
print(heapq.heappop(li))

print(heapq.nlargest(5, li))
print(heapq.nsmallest(5, li))

归并

思路

# 假设现在的列表分两段有序，如何将其合成为一个有序列表，这种操作称为一次归并

# 分解：将列表越分越小，直至分成一个元素
终止条件：一个元素是有序的
合并：将两个有序列表归并，列表越来越大
时间复杂度：O(nlogn)
空间复杂度O(n)

将一个列表分成两段有序的列表

# 假设现在列表分两段有序，将其合成一个有序列表
def merge(li, low, mid, high):
    li_tmp = []  # 定义一个空列表，用来放置排序后的值
    i = low  # li[low:mid+1] 可以表示前半部分的有序列表
    j = mid + 1  # li[mid+1:high+1] 可以表示后半部分的有序列表
    while i <= mid and j <= high:  # 表示前后两部分都有值
        if li[i] <= li[j]:
            li_tmp.append(li[i])
            i += 1
        else:
            li_tmp.append(li[j])
            j += 1

    while i <= mid:  # 下面这两个while循环语句只会有一个执行
        li_tmp.append(li[i])
        i += 1
    while j <= high:
        li_tmp.append(li[j])
        j += 1

    for i in range(len(li_tmp)):
        li[low + i] = li_tmp[i]  # 将排好序的列表赋值回原来的列表

归并排序

def merge_sort(li, low, high):  # 归并排序
    if low < high:  # 两个以上元素
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid + 1, high)
        # print(li[low:mid+1], li[mid+1:high+1])
        merge(li, low, mid, high)
        # print(li[low:high + 1])

加装饰器的归并排序

def _merge_sort(li, low, high):
    if low < high:  # 两个以上元素
        mid = (low + high) // 2
        _merge_sort(li, low, mid)
        _merge_sort(li, mid + 1, high)
        # print(li[low:mid+1], li[mid+1:high+1])
        merge(li, low, mid, high)
        # print(li[low:high + 1])


@cal_time
def merge_sort(li):
    _merge_sort(li, 0, len(li) - 1)

函数的调用

li = list(range(100000))
random.shuffle(li)
merge_sort(li,0,len(li)-1)  # 不带装饰器的调用
# merge_sort(li)
print(li)

总结

LB三人组总结
时间复杂度都是O(n2)
空间复杂度都是O(1)


NB三人组总结
三种排序算法的时间复杂度都是O(nlogn)
一般情况下，就运行时间而言：快排<归并<堆排

三种算法的缺点：
快排：极端情况下排序效率低
归并：需要额外的内存开销（内存栈的开销）
堆排：在排序算法中相对较慢

希尔排序

# 思路

# 希尔排序是一种分组插入排序算法。
首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；
取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。

# 希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。

 代码实现

import random
from timewrap import *


def insert_sort_gap(li, d):
    for i in range(d, len(li)):
        # i 表示无序区第一个数
        tmp = li[i] # 摸到的牌
        j = i - d # j 指向有序区最后位置
        while j >= 0 and li[j] > tmp:
            #循环终止条件： 1. li[j] <= tmp; 2. j == -1
            li[j+d] = li[j]
            j -= d
        li[j+d] = tmp

@cal_time
def shell_sort(li):
    d = len(li) // 2
    while d > 0:
        insert_sort_gap(li, d)
        d = d // 2

li = list(range(10000))
li.sort()
random.shuffle(li)
#print(li)
shell_sort(li)

计数排序

现在有一个列表，已知列表中的数范围都在0到100之间。设计算法在O(n)时间复杂度内将列表进行排序。

创建一个列表，用来统计每个数出现的个数

代码实现

def count_sort(li, max_num):
   count = [0 for i in range(max_num + 1)]
   for num in li:
       count[num] += 1
   i = 0
   for num,m in enumerate(count):
       for j in range(m):
           li[i] = num
           i += 1

桶排序

在计数排序中，如果元素的范围比较大（比如在1到1亿之间），如何改造算法？
桶排序(Bucket Sort)：首先将元素分在不同的桶中，在对每个桶中的元素排序。


桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。
平均情况时间复杂度：O(n+k)
最坏情况时间复杂度：O(n2k)
空间复杂度：O(nk)

 基数排序

# 多关键字排序：加入现在有一个员工表，要求按照薪资排序，薪资相同的员工按照年龄排序。
# 先按照年龄进行排序，再按照薪资进行稳定的排序。
对32,13,94,52,17,54,93排序，是否可以看做多关键字排序？

 代码实现

import random
from timewrap import cal_time

def int2list(num):
    li = []
    while num > 0:
        li.append(num % 10)
        num = num // 10
    li.reverse()
    return li


def get_digit(num, i):
    return num // (10 ** i) % 10


def list_to_bucket(li, i):
    buckets = [[] for _ in range(10)]
    for val in li:
        digit = val // (10 ** i) % 10
        buckets[digit].append(val)
    return buckets

def bucket_to_list(buckets):
    li = []
    for bucket in buckets:
        for val in bucket:
            li.append(val)
    return li
    # return [val for bucket in buckets for val in bucket]

@cal_time
def radix_sort(li):
    max_val = max(li) # 10000
    i = 0
    while 10 ** i <= max_val:
        li = bucket_to_list(list_to_bucket(li, i))
        i += 1
    return li

@cal_time
def sys_sort(li):
    li.sort()


# 0 10000000000000000000000000000
li = list(range(100000))
random.shuffle(li)
#sys_sort(li)

radix_sort(li)

时间复杂度：O(kn)

空间复杂度：O(k+n) (k表示数字位数)