数据结构与算法

冒泡排序_思路及代码

"""
排序算法稳定性介绍：
    概述：排序算法= 把一串数据按照升序或者降序的方式进行排列 方法、思维、方式
    分类：
        稳定排序算法
            排序后，想同元素的相对位置不发生改变
        不稳定排序算法
            排序后，想同元素的相对位置发生改变
    冒泡排序：
        原理：相邻元素两两比较，大的往后走，这样第一轮比较厚，最大值在最大索引处
        重复该动作，只要排序完毕。
    核心：
        1：比较的总轮数        列表的长度-1
        2：每轮比较的总次数     列表的长度-1-当前轮数的索引
        3：谁和谁比较 ？        列表[j]和列表[j+1]
    分析流程： 假设元素个数5个 ，具体如下： [5,3,4,7,2]  长度为5
        比较的轮数,i                     每轮比较的次数,j
        第一轮：索引0                     4->5-1-0
        第二轮:索引1                      3->5-1-1
        第三轮：索引2                     2->5-1-2
        第四轮:索引3                      1->5-1-3
总结：
    冒泡排序属于 稳定
    最优的时间复杂度多少 ？ o(n)
    最坏的时间复杂度多少？o(n²)

"""
# 冒泡排序函数
def bubble_sort(my_list):
    # 1、获取列表的长度  n代表列表长度
    n = len(my_list)
    # 定义循环，  外循环控制比较的轮数  内循环控制比较次数
    for i in range(n - 1):  # i 0 1 2 3
        for j in range(n - 1 - i):
            # 具体的比较动作：相邻的两两元素比较，大的往后
            if my_list[j] > my_list[j + 1]:
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]

my_list=[5,3,4,7,2]
print(f"排序前:{my_list}")
bubble_sort(my_list)
print(f"排序后:{my_list}")

选择排序_思路及代码

• 思路分析

  

• 代码实现

  """
  选择排序介绍：
      原理：
          每轮都假设该轮最前面的那个元素为最小值，然后去 剩下的列表中去寻找真正的最小值。
          最终交换即可。这样就找到了本轮的最小值。重复以上步骤即可。
      大白话：
          第一轮，假设i=0位置的元素是最小值。然后用min_index记住他索引，然后去剩下的所有元素中
          寻找最小值，找到了用min_index做记录。最终判断i和min_index是否交换。第一轮完毕后。
          最小值就在最小索引处。  重复该步骤，直至排序完成。
      分析流程：
          假设5个元素
              第几轮（索引）       该轮比较总次数          公式（具体的谁和谁比较）
              第一轮（0）              4次               索引0和1,2,3,4比较
              第二轮(1)               3次               索引1和2,3,4比较
              第三轮(2)               2次               索引2和3,4比较
              第四轮(3)               1次               索引3和4比较
      要点：
          1：比较的总轮数            列表长度-1
          2：每轮比较总次数          i+1 ~列表长度
          3:谁和谁比较？            索引min_index（初始i）和索引j比较，索引i和索引min_index的值交换
  """
  def select_sort(my_list):
      # 获取列表长度
      n = len(my_list)
      # 外层循环控制比较轮数
      for i in range(n - 1):
          # 定义变量min_index,记录本轮最小值的索引
          min_index = i
          # 内循环控制 每次比较轮数：次数
          for j in range(i + 1, n):  # 1234  234 34  4
              # 具体的比较过程,索引min_index和索引j比较
              if my_list[j] < my_list[min_index]:
                  min_index = j
          # 走到这里了。说明本轮已经找到最小值了，判断，并交换
          if min_index != i:
              my_list[min_index], my_list[i] = my_list[i], my_list[min_index]
  
  if __name__ == '__main__':
      my_list = [5, 3, 4, 7, 2]
      print(f"排序前:{my_list}")
      select_sort(my_list)
      print(f"排序后:{my_list}")

插入排序_思路及代码

"""
插入排序介绍：
    原理：
        把列表分为两个部分，假设第一个元素是有序的，剩下的是无序的。
        每次都从无序的中获取一个元素。和有序前面的元素进行比较
        决定出他的位置，进行插入。直至无序列表的元素操作完毕。剩下的列表就是：有序的
    分析流程：
        假设共有5个元素
            第几轮             该轮数的比较总次数           公式（具体谁和谁比较）
            第1轮                 1次                     索引1和索引0进行比较
            第2轮                 2次                     索引2和索引1 ，索引2和索引0比较
            第3轮                 3次                     索引3和2  索引3和1 索引3和0
            第4轮                 4次                     索引4和3  索引4和2  索引4和1 索引4和0
    要点：
        1：比较总轮数               列表长度-1                range(1,n)
        2：每轮比较的总次数                                  range(i,0,-1)
        3：谁和谁比较               索引j和索引j-1位置的元素比较
    最优：O(n)
    最差：O(n²)
    稳定 ？？？  稳定排序
"""
def insert_sort(my_list):
    n = len(my_list)
    for i in range(1, n):
        for j in range(i, 0, -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__':
    my_list = [5, 3, 4, 7, 2]
    print(f"排序前:{my_list}")
    insert_sort(my_list)
    print(f"排序后:{my_list}")

二分查找

"""
二分（折半）查找：
    概述：
        属于查找类的算法，相对来说效率比较高。时间复杂度 o(log n)
    前提：
        列表必须有序
    原理：
        1：比较 要查找元素和列表中的值，如果一样则返回True。程序结束
        2：如果 要查找的元素比中值小，去前半段（中值前）查找。
        3：如果 要查找的元素比中值大，去后半段（中值后）查找。
        4：重复上述动作，直至找完。如果找完了，还找不到。就返回False
"""
# my_list 原列表   target要查找的目标值
def binary_search_re(my_list, target):
    # 获取列表长度
    n = len(my_list)
    # 判断列表是否为空
    if n == 0:
        return False
    mid = n // 2
    # 比较 要查找的元素 和 中值
    if my_list[mid] == target:
        return True
    elif target < my_list[mid]:
        # 如果要查找的元素 比中值小 ，去前半段（中值前查找）。递归调用
        # [:mid] 采用切片 ，包左不包右
        return binary_search_re(my_list[:mid], target)
    else:
        return binary_search_re(my_list[mid + 1:], target)
    return False


if __name__ == '__main__':
    my_list = [2, 3, 5, 6, 8, 10, 16, 18, 20]
    print(binary_search_re(my_list,60))

自定义代码模拟二叉树

• 图解

  

• 代码框架

  # 定义Node类，表示二叉树节点
  class Node:
      # 初始化属性
      def __init__(self, item):
          self.item = item
          self.lchild = None
          self.rchild = None
  
  
  # 自定义BinaryTree ，表示二叉树
  class BinaryTree:
      def __init__(self, node=None):
          self.root = node
  
      # 定义add函数，表示添加节点
      def add(self, item):
          # 1.item封装为节点
          new_node = Node(item)
          # 2.判断根节点是否为null，如果为空，设置当前节点为跟节点
          if self.root is None:
              self.root = new_node
              return
          # 3.创建一个队列，添加根节点到队列中
          queue = []
          queue.append(self.root)
          # 4.通过while True 死循环 找到空缺的节点位置
          while True:
              # 5.获取队列第一个元素
              node = queue.pop(0)
              # 6.判断当前节点左子树是否为空
              if node.lchild is None:
                  # 6.1把新节点当做当前节点的左子树，并结束
                  node.lchild = new_node
                  return
              else:
                  # 6.2走到这里，说明左子树不为空，把当前节点的左子树添加队列中
                  queue.append(node.lchild)
  
              # 7.判断当前节点的右子树是否为空
              if node.rchild is None:
                  # 7.1把新节点设置为当前节点的右子树 ，并结束
                  node.rchild = new_node
                  return
              else:
                  # 走到这里，说明右子树不为空，把当前节点的右子树，添加到队列中
                  queue.append(node.rchild)
  
      # 定义遍历二叉树 广度优先遍历  （逐层遍历，一层一层的遍历）
      def breadth(self):
          # 1.判断根节点是否为空
          if self.root is None:
              return
          # 2.创建队列
          queue = []
          queue.append(self.root)
          # 3.循环打印内容
          while len(queue) != 0:
              # 4.获取第一个元素
              node = queue.pop(0)
              # 5.打印该节点的元素域
              print(node.item, end=" ")
              # 6.判断当前节点的左子树是否存在，存在添加到队列中
              if node.lchild is not None:
                  queue.append(node.lchild)
  
              # 7.判断当前节点的右子树是否存在，存在添加到队列中
              if node.rchild is not None:
                  queue.append(node.rchild)
  
      # 深度优先之先序遍历（根左右）
      def preorder(self, root):
          # 1.判断根节点是否不为空，不为空才打印
          if root is not None:
              print(root.item, end=" ")
              # 递归遍历左子树
              self.preorder(root.lchild)
              # 递归遍历右子树
              self.preorder(root.rchild)
  
      # 深度优先之中序遍历（左根右）
      def inorder(self, root):
          # 1.判断根节点是否不为空，不为空才打印
          if root is not None:
              # 递归遍历左子树
              self.inorder(root.lchild)
              print(root.item, end=" ")
              # 递归遍历右子树
              self.inorder(root.rchild)
  
      # 深度优先之后序遍历（左右根）
      def postorder(self,root):
          if root is not None:
              #遍历左子树
              self.postorder(root.lchild)
              #遍历右子树
              self.postorder(root.rchild)
              #打印根节点
              print(root.item,end=" ")
  
  
  def dm1_1_测试节点和二叉树类():
      # 1-创建节点
      node1 = Node("A")
      # 打印节点的元素域   左子树  右子树
      print(node1.item)  # a
      print(node1.lchild)  # None
      print(node1.rchild)  # None
  
      print("--------二叉树类----------")
      # #创建了一个空树
      # bt = BinaryTree()
      # print(bt.root)   #None
  
      print("--------测试二叉树----------")
      bt = BinaryTree(node1)
      print(bt.root)  # <__main__.Node object at 0x000001E7F19438B0>
      print(bt.root.item)
      print(bt.root.lchild)
      print(bt.root.rchild)
  
  
  def dm2_2_测试添加节点():
      bt = BinaryTree()
      # 添加元素
      bt.add("A")
      bt.add("B")
      bt.add("C")
      bt.add("D")
      bt.add("E")
      bt.add("F")
      bt.add("G")
      bt.add("H")
      bt.add("I")
      bt.add("J")
  
  
  def dm3_3_测试添加_遍历节点():
      bt = BinaryTree()
      # 添加元素
      bt.add("A")
      bt.add("B")
      bt.add("C")
      bt.add("D")
      bt.add("E")
      bt.add("F")
      bt.add("G")
      bt.add("H")
      bt.add("I")
      bt.add("J")
      bt.breadth()
  
  
  def dm4_4_测试深度优先_先序遍历节点():
      bt = BinaryTree()
      # 添加元素
      bt.add("A")
      bt.add("B")
      bt.add("C")
      bt.add("D")
      bt.add("E")
      bt.add("F")
      bt.add("G")
      bt.add("H")
      bt.add("I")
      bt.add("J")
      print("先序遍历（根左右）")
      bt.preorder(bt.root)
      print()
      print("中序遍历（左根右）")
      bt.inorder(bt.root)
      print()
     print("后序遍历（左右根）")
      bt.postorder(bt.root)
  
  
  
  if __name__ == '__main__':
      # dm1_1_测试节点和二叉树类()
      # dm2_2_测试添加节点()
      # dm3_3_测试添加_遍历节点()
      dm4_4_测试深度优先_先序遍历节点()

  根据中序和先序_逆推二叉树结构