python进阶篇-day09-数据结构与算法(非线性结构与排序算法)

非线性结构(树状结构)

特点: 每个节点都可以有n个子节点(后继节点) 和 n个父节点(前驱节点)

代表: 树, 图......

概述

属于数据结构之 非线性结构的一种, 父节点可以有多个子节点(后续节点)

特点

1. 有且只有1个根节点

2. 每个节点都可以有1个父节点及任意个子节点, 前提: 根节点除外(没有父节点)

3. 没有子节点的节点称之为: 叶子节点

二叉树概念和性质

每个节点最多只能有2个子节点

二叉树分类:

1. 完全二叉树: 除了最后1层, 其他层的节点都是满的

2. 满二叉树: 包括最后1层, 所有层的节点都是满的

3. 不完全二叉树: 某层(不仅仅是最后1层)的节点数量不满

常用二叉树:

1. 平衡二叉树: 防止树退化成链表, 指的是: 任意节点的两颗子树的高度差不超过1

2. 排序二叉树: 主要是对元素排序的

存储方式

更推荐使用 链表的方式来存储, 每个节点有三部分组成, 分别是: 元素域(数值域), 左子树(地址域), 右子树(地址域)

针对于, 多叉树的情况, 可以将其转成二叉树, 然后再来存储

性质

1. 在二叉树的第i层上至多有2i-1 个结点（i>0）eg：第3层最多结点个数2^((3-1))

2. 深度为k的二叉树至多有2k - 1个结点（k>0）eg:层次2^((3))-1= 7

3. 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0 = N2+1

4. 最多有n个结点的完全二叉树的深度必为log2(n+1)

5. 对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1,其父节点的编号必为i//2（i＝1时为根,除外）

二叉树的广度优先

广度优先可以找到最短路径：

相当于层次遍历，先把第层给遍历完，看有没有终点；再把第层遍历完，看有没有重点

插入节点

1. 初始操作：

   初始化队列、将根节点入队、准备加入到二叉树的新结点

2. 重复执行：

   获得并弹出队头元素

   1、若当前结点的左右子结点不为空，则将其左右子节点入队列

   2、若当前结点的左右子节点为空，则将新结点挂到为空的左子结点、或者右子节点

图示

二叉树的深度优先

深度优先往往可以很快找到搜索路径：

比如：先找一个结点看看是不是终点，若不是继续往深层去找，直到找到终点。、中序，先序，后序属于深度优先算法

示例

层次(广度)遍历: 0123456789

先序遍历: 0137849256 根 左 右

中序遍历: 7381940526 左 根 右

后序遍历: 7839415620 左 右 根

图示

二叉树代码演示

# 创建节点类
class Node(object):# 初始化属性def __init__(self, item):self.item = item  # 数值域self.lchild = None  # 左子树(地址域)self.rchild = None  # 左子树(地址域)
​
​
# 创建二叉树类
class BinaryTree(object):def __init__(self, root: Node = None):self.root = root  # 根节点
​# 添加元素函数(完全二叉树)def add(self, item):# 判断根节点是否为空if self.root is None:self.root = Node(item)return# 根节点不为空, 找到缺失节点# 创建队列, 用于记录已存在的节点queue = []# 把根节点添加到队列queue.append(self.root)# 循环遍历队列, 直至 把新元素添加到合适的位置while True:# 获取队列中的第一个元素node = queue.pop(0)# 左子树为空if node.lchild is None:node.lchild = Node(item)return  # 结束添加动作else:# 左子树存在, 就将其添加到队列中queue.append(node.lchild)# 右子树为空if node.rchild is None:node.rchild = Node(item)return  # 结束添加动作else:# 右子树存在, 就将其添加到队列中queue.append(node.rchild)
​# 广度优先def breadth_travel(self):# 判断根节点是否为空if self.root is None:return  # 为空直接结束# 创建队列, 记录所有节点queue = []# 将根节点, 添加到队列中queue.append(self.root)# 只要队列长度大于0, 就说明还有节点, 循环遍历while len(queue) > 0:# 获取队列中的第一元素node = queue.pop(0)# 输出当前节点print(node.item, end='\t')# 判断当前节点的左子树是否为空if node.lchild is not None:# 不为空, 则将左子树入队queue.append(node.lchild)# 判断当前节点的右子树是否为空if node.rchild is not None:# 不为空, 则将左子树入队queue.append(node.rchild)
​# 深度优先: 先序(根左右)def preorder_travel(self, root):# 判断根节点是否不为空if root is not None:# 中序先输出根节点print(root.item, end='\t')# 递归左子树self.preorder_travel(root.lchild)# 递归右子树self.preorder_travel(root.rchild)
​# 深度优先: 中序(左根右)def mid_travel(self, root):if root is not None:self.mid_travel(root.lchild)print(root.item, end='\t')self.mid_travel(root.rchild)
​# 深度优先: 后序(左右根)def poster_travel(self, root):if root is not None:self.poster_travel(root.lchild)self.poster_travel(root.rchild)print(root.item, end='\t')
​

三. 算法

排序类相关

稳定性: 排序前后的相对位置(相同的元素位置)是否发生变化

稳定排序: 冒泡排序、插入排序、归并排序和基数排序

不稳定排序: 选择排序、快速排序、希尔排序、堆排序

冒泡排序

原理

相邻元素两辆比较, 大的往后走, 这样第一轮比较完毕后, 最大值就在最大索引处

核心

1. 比较的总轮数 列表长度 - 1

2. 每轮比较的总次数 列表长度 - 1 - 轮数(从0 开始)

3. 谁和谁比较(交换) j 和 j + 1 比较

图解

代码

def buble_sort(my_list):# 定义变量n存储列表长度n = len(my_list)# 比较的轮数for i in range(n - 1):  # i: 0, 1, 2, 3# 记录交换的次数count = 0# 每轮比较的次数for j in range(n - 1 - i):  # j: 4, 3, 2, 1if my_list[j] > my_list[j + 1]:# 交换时计数器加一count += 1my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]print(f'第 {i} 轮交换了 {count} 次')# 如果当前轮次交换了0次, 则跳出外循环if count == 0:break
​
​
if __name__ == '__main__':list1 = [2, 1, 4, 5, 3]buble_sort(list1)print('list1', list1)print('-' * 21)
​list2 = [5, 3, 4, 7, 2]buble_sort(list2)print('list2', list2)
​

冒泡总结

时间复杂度: 最优O(n), 最差O(n²)

遍历一遍发现没有任何元素发生了位置交换,终止排序

算法稳定性:稳定算法

选择排序

原理

第一轮: 假设索引为0的元素时最小值, 依次和后续的元素比较, 只要比该值小, 就纪录住真正最小值的那个索引, 第一轮比较完毕后, 把最小值放到索引为0的位置即可

第二轮: 假设索引为1的元素时最小值, 依次和后续的元素比较, 只要比该值小, 就纪录住真正最小值的那个索引, 第一轮比较完毕后, 把最小值放到索引为1的位置即可

......

解释:

选择排序就是把符合要求的数据选择出来进行排序

核心

1. 比较的总轮数 列表长度 - 1

2. 每轮比较的总次数 i + 1 ~ 列表的最后1个元素

3. 谁和谁比较(交换) j 和 min_index 位置的元素比较

比较过程

具体的比较过程, 假设共 5 个元素 比较的轮数 每轮比较的总次数 谁和谁比较 第0轮 4 0和1, 0和2, 0和3, 0和4 第1轮 3 1和2, 1和3, 1和4 第2轮 2 2和3, 2和4 第3轮 1 3和4

代码

def select_sort(my_list):# 定义变量n存储列表长度n = len(my_list)# 比较的轮数for i in range(n - 1):  # i: 0, 1, 2, 3# 记录最小值索引min_idx = i# 每轮比较的次数for j in range(i + 1, n):  # j: 4, 3, 2, 1# 判断min_idx后的元素是否比min_idx小if my_list[j] < my_list[min_idx]:# 将最小值索引设为jmin_idx = j# 如果最小值索引等于i说明i的位置是正确的,不交换if min_idx != i:# 交换my_list[i], my_list[min_idx] = my_list[min_idx], my_list[i]
​
​
if __name__ == '__main__':list1 = [2, 1, 4, 5, 3]select_sort(list1)print('list1', list1)print('-' * 21)
​list2 = [5, 3, 4, 7, 2]select_sort(list2)print('list2', list2)
​

选择总结

算法稳定性: 不稳定算法

时间复杂度: 最优: O(n²), 最差: O(n²)

插入排序

原理

把要排序的列表分成两部分, 第一部分是有序的(拍好序的), 第二部分是无序的(待排序的), 然后从待排序的列表中, 依次取出每个值, 插入到 排好序的列表的 合适位置 .

核心

1. 比较的总轮数 列表长度 - 1 for i in range(1, n)

2. 每轮比较的总次数 i ~ 0(逆向遍历) for i in range(i, 0, -1)

3. 谁和谁比较(交换) i 和 j 的每个值 比较

比较过程

具体的比较过程, 假设共 5 个元素 比较的轮数 每轮比较的总次数 谁和谁比较 第1轮 4 1和0 第2轮 3 2和1, 2和0 第3轮 2 3和2, 3和1, 3和0 第4轮 1 4和3, 4和2, 4和1, 4和0

代码

def insert_sort(my_list):# 定义变量n存储列表长度n = len(my_list)# 比较的轮数for i in range(1, n):           # i: 1,  2,   3,     4# 每轮比较的次数for j in range(i, 0, -1):   # j: 1  2,1  3,2,1  4,3,2,1# 判断当前元素(待排序)是否比前面的元素(排好序的)小if my_list[j] < my_list[j - 1]:# 交换当前元素和当前元素的前一个元素my_list[j], my_list[j - 1] = my_list[j - 1], my_list[j]else:break
​
​
if __name__ == '__main__':list1 = [2, 1, 4, 5, 3]insert_sort(list1)print('list1', list1)print('-' * 21)
​list2 = [5, 3, 4, 7, 2]insert_sort(list2)print('list2', list2)
​

插入总结

算法稳定性: 稳定算法

时间复杂度: 最优: O(n) 最坏: O(n²)

查找类相关(二分查找)

此处只记录二分查找, 并非查找只有二分查找这一种

介绍

1. 概述: 他是一种高效的查找类算法, 也叫: 折半查找

2. 细节: 要被查找的列表必须是有序的

1. 原理:

   1. 获取列表的中间位置的元素, 然后和要查找的元素进行比较

   2. 如果相等, 直接返回结果即可

   3. 如果比中间值小, 去 中间前 范围查找

   4. 如果比中间值大, 去 中间后 范围查找

递归版

def binary_search(my_list, item):n = len(my_list)if n <= 0:return Falsemid = n // 2if item == my_list[mid]:return Trueelif item < my_list[mid]:return binary_search(my_list[:mid], item)else:return binary_search(my_list[mid + 1:], item)

非递归版

def binary_search(my_list, item):# 计算列表长度n = len(my_list)# 定义初始起始位置为0start = 0# 定义初始终止位置为列表长度减1end = n - 1# 当起始位置大于终止位置时结束循环while start <= end:# 定义中间位置为起始位置加终止位置除2mid = (start + end) // 2# 判断中间索引位置的元素是否为要查找的元素if my_list[mid] == item:return True# 判断中间索引位置的元素比要查找的位置小elif my_list[mid] < item:# 设置起始位置索引为中间位置加1start = mid + 1# 判断中间索引位置的元素比要查找的位置大else:# 设置终止位置索引为中间位置减1end = mid - 1return False
​
​
if __name__ == '__main__':list1 = [1, 2, 3, 4, 5, 6, 7]print(binary_search(list1, 4))
​
​

总结

1. 必须采用顺序存储结构

2. 必须按关键字大小有序排列

3. 时间复杂度: 最优: O(1) 最坏: O(logn)