Python学习-数据结构与算法02

Python学习-数据结构与算法02简单排序相关概念冒泡排序简单选择排序直接插入排序复杂排序-快速排序线性表查找顺序查找折半查找树基本概念分类二叉树的性质树的遍历二叉树的遍历代码实现简单排序相关概念排序给定一个元素序列{r1,r2,…,rn}按照每个元素的关键码{k1,k2,…,kn}将元素重新排列使关键码从小到大正序或从大到小逆序排列。稳定性在待排序的文件中多个关键码相同的元素经排序后元素之间的相对次序保持不变则称此排序方法是稳定的若排序后相对次序发生改变则称为是不稳定的。冒泡排序属于交换排序其思想是从前向后两两比较相邻元素逆序就交换每一轮把最大的元素 “冒泡” 到末尾。重复上述步骤直至没有逆序的元素为止。属于稳定排序。时间复杂度最好-O(n)最坏-O(n²)。# 冒泡排序defbubble_sort(arr):nlen(arr)# 排序的轮数foriinrange(n-1):# 每轮排序的次数forjinrange(n-1-i):ifarr[j]arr[j1]:# 交换arr[j],arr[j1]arr[j1],arr[j]if__name____main__:arr[5,3,8,4,2]bubble_sort(arr)print(arr)# [2, 3, 4, 5, 8]优化若某一轮没有发生任何交换说明已经有序可以提前退出# 冒泡排序defbubble_sort(arr):nlen(arr)# 排序的轮数foriinrange(n-1):# 每轮排序的次数count0forjinrange(n-1-i):ifarr[j]arr[j1]:# 交换arr[j],arr[j1]arr[j1],arr[j]count1print(f第{i1}轮交换次数为{count})ifcount0:break简单选择排序基本思想每次从未排序区间里选出最小或最大的元素放到已排序区间的末尾使有序序列不断增长直至全部排序完毕。属于不稳定排序。时间复杂度最好-O(n²)最坏-O(n²)。# 简单选择排序defselect_sort(arr):nlen(arr)# 排序的轮数foriinrange(n-1):# 假设未排序区第一个元素是最小值min_idxi# 在未排序区找真正最小值下标forjinrange(i1,n):ifarr[j]arr[min_idx]:min_idxj# 最小值下标发生变化进行交换把最小值放到已排序区末尾ifmin_idx!i:arr[i],arr[min_idx]arr[min_idx],arr[i]直接插入排序基本思想每次从未排序部分拿第一个元素在已排序部分里找到合适位置插入直到全部有序。把需要排序的数组分成两部分已经排好序的有序区通常默认数组的第一个数字为有序区、未排序的无序区。属于稳定排序。时间复杂度最好-O(n)最坏-O(n²)。# 简单插入排序definsert_sort(arr):nlen(arr)foriinrange(n-1):forjinrange(i1,0,-1):ifarr[j]arr[j-1]:arr[j],arr[j-1]arr[j-1],arr[j]else:break复杂排序-快速排序快速排序是冒泡排序的改进算法冒泡排序中元素的比较和移动都是在相邻位置进行需要进行多次才能排序完成快速排序中元素的比较和移动从两端向中间进行。基本思想在分区中选择一个元素作为轴值将待排序元素划分为两个分区使左侧元素均小于等于轴值右侧元素均大于等于轴值分别在两个分区上重复上述步骤直到整个序列有序。属于不稳定排序。时间复杂度最好-O(nlogn)最坏-O(n²)。# 复杂排序-快速排序defquick_sort(arr,first,end): 快速排序 :param arr: 待排序的列表 :param first: 待排序区间的左界 :param end: 待排序区间的左界 iffirstend:returnleftfirst rightend# 保存第一个元素作为基准轴pivotarr[first]whileleftright:# 右侧扫描寻找小于pivot的元素前移# 右侧大于pivot的元素right减一前移 → 右侧大的仍在右侧whileleftrightandarr[right]pivot:right-1arr[left]arr[right]# 左侧扫描寻找大于pivot的元素后移# 左侧小于pivot的元素left加一后移 → 左侧小的仍在左侧whileleftrightandarr[left]pivot:left1arr[right]arr[left]# 循环结束已找到基准轴元素的位置arr[left]pivot# 递归继续处理左侧区数据quick_sort(arr,first,left-1)# 递归继续处理左侧区数据quick_sort(arr,right1,end)线性表查找顺序查找从第一个元素开始从前向后逐个匹配找到就返回位置找不到就查找失败。特点不要求表有序顺序表、链表都能用简单但查找效率慢。时间复杂度O(n)# 顺序查找defseq_search(arr,key):foriinrange(len(arr)):ifarr[i]key:returni# 找到返回下标return-1# 没找到折半查找又称为二分查找其基本思想为先确定待查找元素所在的范围逐步缩小范围直到找到或找不到查找失败为止。特点比较次数少查找速度快但只能用于有序顺序表链表不能用二分查找。假设线性表是升序排列的即每次用中间元素和目标比较中间值 目标 → 找到目标更小 → 去左半边找目标更大 → 去右半边找不断缩小范围直到找到或为空。# 二分查找defbinary_search(arr,key): 二分查找,假设arr升序排列 :param arr: 待查找数组/列表... :param key: 需要查找的元素 :return: 找到则返回索引未找到则返回False left0rightlen(arr)-1whileleftright:# 获取列表中值的索引mid(leftright)//2ifkeyarr[mid]:returnmidelifkeyarr[mid]:rightmid-1else:leftmid1returnFalse根据折半查找的思想也可采用递归的方式实现## 递归实现defbinary_search_recursive(arr,key,left0,rightNone):# 初始化rightifrightisNone:rightlen(arr)-1# 递归出口查找区间不存在ifleftright:returnFalsemid(leftright)//2ifkeyarr[mid]:returnmid# 返回原数组下标elifkeyarr[mid]:returnbinary_search_recursive(arr,key,left,mid-1)else:returnbinary_search_recursive(arr,key,mid1,right)returnFalse树树型结构是典型的非线性数据结构是由有限个结点组成的一个具有层次关系的集合。特点每个结点有零个或多个子节点每个子结点只有一个父结点没有前驱的结点为根节点有且只有一个根节点除了根结点之外每个子结点可分成若干互不相交的子树。基本概念结点的度一个结点含有的子树的个数。树的度一个树中最大的结点的度。叶结点度为零的结点。分支结点度不为零的结点。孩子结点一个结点子树的根结点。双亲结点含有孩子结点的结点。兄弟结点具有相同双亲结点的结点。祖先结点从根到该结点所经分支上的所有节点。子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙结点。结点层次从根开始定义为第一层根的子结点为第二层逐次往下递推。路径从根结点到某一结点的一条通道。路径长度路径经过的边的个数。分类无序树树中任意结点的子结点之间没有顺序关系。有序树树中任意结点的子结点之间有顺序关系。二叉树每个结点最多有两个子树的有序树。满二叉树所有叶结点均位于最后一层其他分支结点的度数均为2完全二叉树扣除最深层后成为一棵满二叉树且最后一层的所有结点均向左靠齐。平衡二叉树当且仅当任何结点的两颗子树的高度差不大于1的二叉树。排序二叉树若左子树不为空则左子树上所有结点的值均小于其根结点的值若右子树不为空则右子树上所有结点的值均大于其根结点的值。二叉树的性质一棵非空二叉树的第 i 层上至多有2i-1个结点。深度为 h 的二叉树至多有2h-1个结点。对于任何一棵二叉树其叶结点数为n0度为2的结点数为n2则n0n21。对于具有 n 个结点的完全二叉树若按照从上到下同一层次上结点从左到右的顺序对所有结点从1开始顺序编号则对于序号为 i 的结点其左孩子结点为 2i 右孩子结点为 2i1父结点为 [i/2]表示取整根结点除外。树的遍历按照某种次序访问树中的所有结点使每个结点被访问且仅被访问一次。1前序遍历先访问根结点再按照从左到右的顺序前序遍历根结点的每一颗子树。2后序遍历先按照从左到右的顺序后序遍历根结点的每一颗子树再访问根结点。3层序遍历也称广度遍历从树的第一层即根结点开始自上而下逐层遍历每层按照从左到右的顺序逐个访问结点。二叉树的遍历分为三种前序遍历、中序遍历、后序遍历。深度优先遍历DFSDepth-First Search1前序根结点→前序遍历根结点左子树→前序遍历根结点右子树2中序中序遍历根结点左子树→根结点→中序遍历根结点右子树3后序后序遍历根结点左子树→后序遍历根结点右子树→根结点。广度优先遍历BFSBreadth-First Search层序遍历。代码实现定义结点类和二叉树类采用广度优先遍历# 定义结点类classNode:def__init__(self,data):self.datadata self.leftNone# 左子树self.rightNone# 右子树# 定义二叉树类classBinaryTree:def__init__(self,nodeNone):self.rootnode# 添加结点defadd(self,data):new_dataNode(data)# 判断根结点是否为空若为空设置当前结点为根结点ifself.rootisNone:self.rootnew_datareturn# 创建队列queue[]queue.append(self.root)# 根结点入队# 循环whileTrue:# 取出队列中的第一个元素nodequeue.pop(0)# 判断该结点左子树是否为空不为空则该元素入队为空则设置当前结点的左子树为新结点ifnode.leftisNone:node.leftnew_datareturnelse:queue.append(node.left)# 判断该结点右子树是否为空不为空则该元素入队为空则设置当前结点的右子树为新结点ifnode.rightisNone:node.rightnew_datareturnelse:queue.append(node.right)# 广度优先遍历defbreadth_fs(self):# 判断根结点是否为空ifself.rootisNone:return# 创建队列根结点入队queue[]queue.append(self.root)# 队列不为空则一直循环遍历whilelen(queue)!0:# 取出队列中的第一个元素即根结点nodequeue.pop(0)# 打印根结点的数据print(node.data,end )# 判断该结点的左子树是否为空不为空则添加至队列中ifnode.leftisnotNone:queue.append(node.left)# 判断该结点的右子树是否为空不为空则添加至队列中ifnode.rightisnotNone:queue.append(node.right)深度优先遍历前序遍历、中序遍历、后序遍历# 前序遍历根→左→右defpre_order(self,root):# 判断根结点是否为空不为空则遍历打印ifrootisnotNone:print(root.data,end )self.pre_order(root.left)self.pre_order(root.right)# 中序遍历左→根→右defin_order(self,root):ifrootisnotNone:self.pre_order(root.left)print(root.data,end )self.pre_order(root.right)# 后序遍历左→右→根defpost_order(self,root):ifrootisnotNone:self.pre_order(root.left)self.pre_order(root.right)print(root.data,end )