算法

递归

递归有两大特性： 　　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 = 0for 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表示数字位数)

转载于:https://www.cnblogs.com/daofaziran/p/10090706.html