算法初识 再讲递归 汉诺塔问题 查找 LowB三人组 NB三人组
算法动画查看
https://www.cnblogs.com/huang-yc/p/9774287.html
或者
递归的两个特点：1、调用自身；2、结束条件。
# 下面那些函数是递归函数 def func1(x): print(x) func1(x-1) def func2(x): if x > 0: print(x) func2(x+1) def func3(x): if x > 0: print(x) func3(x-1) def func4(x): if x>0: func4(x-1) print(x) #思考：func3和func4会打印什么效果？为什么？
下图中：长条表示print打印，方框表示执行函数
func3执行图示
func4执行图示
汉诺塔问题
def hanoi(n, a, b, c): if n > 0: hanoi(n-1, a, c, b) print("moving from %s to %s" % (a, c)) hanoi(n-1, b, a, c)
查找
# 线性查找
def linear_search(li, val): for ind, v in enumerate(li): if v == val: return ind else: return None
# 二分查找 def binary_search(li, val): left = 0 right = len(li) - 1 while left <= right: # 候选区有值 mid = (left + right) // 2 if li[mid] == val: return mid elif li[mid] > val: # 带查找的值在mid左侧 right = mid - 1 else: # li[mid] < val 带查找的值在mid右侧 left = mid + 1 else: return None
LowB三人组
一、冒泡
""" 冒泡排序 一共要走多少趟： 列表长度-1趟（因为最后一个数就不用排了） 无序区范围是多少：
列表的长度-趟数-1 所以是两个循环 比较规律： 列表每相邻的数，如果前面比后面的大，则交换这两个数 一趟排序完成后，则无序区减少一个数，有序区增加一个数
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
代码关键点：
趟 和 无序区范围 两个循环 复杂度是O（n**2） 改进的地方 如果一趟没有发生位置的改变，就说明已经排好序 """ def bubble_sort(li): for i in range(len(li) - 1): exchange = False for j in range(len(li) - i - 1): if li[j] < li[j + 1]: li[j], li[j + 1] = li[j + 1], li[j] exchange = True if not exchange: return
二、选择排序
""" 选出最小的，和第一个位置交换位置， 需要n-1趟 无序区在是哪？ 第几趟到列表最后一个数 怎么判断他是最小的数 先指定无序区第一个就是最小的 两个循环 多少趟 无序区 一趟排序记录最小的数，放到第一个位置 再一趟排序记录记录列表无序区最小的数，放到第二个位置 。。。 算法关键点：有序区和无序区，无序区最小数的位置 O（n**2） """ def select_sort(li): for i in range(len(li) - 1): # 第i趟 min_val = i # 指定第一个为最小值 for j in range(i + 1, len(li)): if li[j] < li[min_val]: min_val = j li[i], li[min_val] = li[min_val], li[i]
三、插入排序
""" 初始：手里（有序区）只有一张牌 每次（从无序区）摸一张牌，插入到手里的牌的正确位置 算法复杂度O（n**2） """ def insert_sort(li): for i in range(1, len(li)): # 因为手上有一张牌,i表示摸到的牌的下标 tmp = li[i] j = i - 1 # j指的是手里的牌的下标 while j >= 0 and li[j] > tmp: # 这个循环就是再找插入的位置 li[j + 1] = li[j] j -= 1 li[j + 1] = tmp
NB三人组
一、快排
""" 要点； 1/取一个元素P，使其归位 2/列表分为两部分，左边都比P小，右边都比P大 3/递归完成 动画实例原理 两个指针由两边向中间移动，分割成以P为边界的左右两边 取出P的值存起来 从右边找出一个比5小的数，放在P之前的位置 从左边找出一个比5大的数，放在，右边空的位置 partition代码是很对称的 复杂度 O（nlogn） 加装饰器，计算排序时间 添加马甲，嵌套函数 问题 最坏情况： 解决：随机找一个数，和第一个数交换位置 递归 """ def partition_(li, left, right): # 先保存第一个数 tmp = li[left] while left < right: while left < right and li[right] >= tmp: # 先从右边开始的 left 小于 right 且right的值比tmp大 right -= 1 # 那就向左移动 li[left] = li[right] # 直到指针碰到left，或者right的值比tmp小，就把right的值赋给left指针的位置 while left < right and li[left] <= tmp: # 然后是左边，找到比tmp小的值，放到右边指针处 left += 1 li[right] = li[left] li[left] = tmp # 最后把tmp 放在 left和right交汇处 return left # 将这个中间值（即最终tmp所在位置的索引，并不是列表形式上的中间值）返回 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)
二、堆排序
""" 堆排序前传-树与二叉树 树是一种数据结构 树是一种可以递归定义的数据结构 树是由n个节点组成的集合： 如果n=0，那这是一棵空树 如果n>0,那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本省又是一棵树 一些概念 根节点，叶子节点（不能分叉的节点） 树的深度（高度） 树的度 （分了几个叉，树的度，就是分叉最多的那个度） 孩子节点/父节点 子树 二叉树 度不超过二的树 每个节点最多有两个孩子 两个孩子节点被区分为左孩子节点和右孩子节点 满二叉树 一个二叉树，如果每一层的节点数都达到最大值，则这个树就是满二叉树 完全二叉树 叶子节点只能出现在最下层和次下层，并且最下面的节点都集中在该层最左边的若干位置的二叉树 二叉树的存储方式（表示方式） 链式存储 顺序存储（堆排序用） 简单来说就是用列表来存 父节点和左孩子节点的编号下标有什么关系 i-->2i+1 父节点和右孩子节点的编号下表有什么关系 i-->2i+2 孩子节点如何得到父节点 i-->(i-1)//2 堆--一种特殊的完全二叉树 大根堆-一棵完全二叉树，满足任一节点都比孩子节点大 小根堆-一棵完全二叉树，满足任一节点都比孩子节点小 堆的向下调整 假设：节点的左右子树都是堆，但自身不是堆 当根节点的左右子树都是堆时，可以通过一次向下调整来将其变换成一个堆 挨个出数 排好序 怎么构造一个堆 农村包围城市， 先看最后一个非叶子节点看起 每次从小的调整，再调整大的 时间复杂度 nlogn 堆排序-内置的模块 import heapq topk问题 现在有n个数，设计算法得到前K大的数 解决思路： 1/排序后切片 nlogn+k 2/排序LowB三人组 kn 维护k长度的列表，如果有新的值，就替换掉 3/堆排序的思路 nlogk 取列表前k个元素建立一个小根堆，堆顶就是目前第K大的数 依次向后遍历原列表，对于列表中的元素， 如果小于堆顶，则忽略该元素 如果大于堆顶，则将堆顶更换为该元素，并对堆进行一次向下调整 遍历列表所有元素后，倒序弹出堆顶 """ def sift(li, low, high, ): """ 向下调整函数 :param li: :param low: 堆的根节点位置 :param high: 堆的最后一个元素的位置，是为了保证向下调整的时候，不会超出堆 :return: """ i = low # i指的的根节点 j = 2 * i + 1 # j指的市左孩子 tmp = li[low] # 把堆顶存起来 while j <= high: # 只要j的位置有数，即没有越界 if j + 1 <= high and li[j + 1] > li[j]: # j+1 <= high 保证右孩子有，并且右孩子比较大 j = j + 1 # 将j指向右孩子 if li[j] > tmp: # 如果孩子比堆顶大 li[i] = li[j] # 就交换孩子到堆顶 i = j # 往下调整一层，即跟新i和j的位置 j = 2 * i + 1 else: # 表示tmp大，即本身的堆顶就是大的值，就不用更换了 li[i] = tmp # 把tmp放到某一级领导的位置 break else: li[i] = tmp # 循环结束，把tmp放到了叶子节点上 # 使用sift 实现堆排序 def heap_sort(li): """ 1/建堆，农村包围城市 2/挨个出数，将堆顶的大数放到最后面high的位置，然后将high向前移一位 :param li: :return: """ # 最后一个非叶子节点的位置 最后一个元素的下标是n-1 n = len(li) for i in range((n - 2) // 2, -1, -1): # i表示建堆的时候调整的部分的根的下标 sift(li, i, n - 1) # 建堆完成了 for i in range((n - 1), -1, -1): # i指向当前堆的最后一个元素 li[0], li[i] = li[i], li[0] # 将堆顶和最后一个数作交换 sift(li, 0, i - 1) # i-1 是新的high # 堆排序解决TopK问题 def topK(li, k): heap = li[:k] for i in range((k - 2) // 2, -1, -1): sift(heap, i, k - 1) for i in range(k, len(li) - 1): if li[i] > heap[0]: heap[0] = li[i] sift(heap, 0, k - 1) for i in range(k-1,-1,-1): heap[0], heap[i] = heap[i], heap[0] sift(li, 0, i-1) return heap
三、归并排序
""" 假设现在的列表分两段有序，如何让将其合成为一个有序列表 2 5 7 8 9 1 3 4 6 两段都指定一个从左开始的指针，并对比大小，小的放下来 这种操作称为一次归并 """ # 先假设两段已经有序, def merge(li, low, mid, high): """ :param li: :param low:第一段的最左边 :param mid:第一段的最右边 :param high:第二段的最右边，即列表的末尾 :return: """ i = low j = mid + 1 new_li = [] while i <= mid and j <= high: # 只要左右两边都有数 if li[i] < li[j]: new_li.append(li[i]) i += 1 else: new_li.append(li[j]) j += 1 # while 执行完毕，肯定有一部分没数了 while i <= mid: new_li.append(li[i]) i += 1 while j <= high: new_li.append(li[j]) j += 1 # 把有序的列表写回去 li[low:high + 1] = new_li """ 归并排序的实现 1/分解：把列表越分越小，直至分成一个元素 2/终止条件：一个元素是有序的 3/合并：将两个有序列表归并，列表越来越大 """ # 基于递归分解 def merge_sort(li, low, high): if low < high: # 至少有两个元素，递归 mid = (low + high) // 2 merge_sort(li, low, mid) merge_sort(li, mid + 1, high) merge(li, low, mid, high) """ 时间复杂度 nlogn 空间复杂度 n 因为和之前的不一样，之前的都是原地排序 """