排序算法
所谓排序，使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
排序算法，就是如何使得记录按照要求排列的方法
排序算法在很多领域是非常重要
在大量数据的处理方面：一个优秀的算法可以节省大量的资源。
在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析
1.算法的稳定性
具有相同关键字的纪录经过排序后，相对位置保持不变，这样的算法是稳定性算法
不稳定的排序算法: 选择排序、快速排序、希尔排序、堆排序
稳定的排序算法: 冒泡排序、插入排序、归并排序和基数排序
2.冒泡排序
重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”
相邻位置两个元素比较, 前面的元素比后面的元素大则交换, 把最大的数给找到经过一轮一轮的比较最终把序列给排序
'''
核心:
1.比较的总轮数 列表的长度 - 1
2.每轮比较的总次数 列表的长度-1 - 轮数
3. 谁和谁交换 j 和 j + 1
'''
def bubble_sort(alist):
'''
自定义函数,冒泡排序
:param alist:
:return:
'''
n = len(alist)
# 定义外循环表示循环的总轮数
for i in range(n - 1):
# 定义变量,记录每轮交换次数
count = 0
# 定义内循环,表示每轮比较的总次数
for j in range(n - 1 - i):
# 具体比较的两个元素交换
if alist[j] > alist[j + 1]:
count += 1
alist[j], alist[j + 1] = alist[j + 1], alist[j]
# 如果本轮没有发生交换,说明已经排好了,无需继续
if count == 0:
return
if __name__ == '__main__':
l = [5, 3, 4, 7, 2]
my_sort(l)
print(l)
3.选择排序
选择排序的工作原理:
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，
然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾. 以
此类推，直到全部待排序的数据元素的个数为零
选择排序就是把符合要求的数据选择出来进行排序
def select_sort(Alist):
'''
自定义函数选择排序
:param Alist:
:return:
'''
n = len(Alist)
for i in range(n):
# 假设第一个为最小值
minnum = Alist[i]
minindex = i
for j in range(i + 1, n):
# 交换最小值索引
if Alist[j] < Alist[i]:
minnum = Alist[j]
minindex = j
# 最小值和第一个交换
if Alist[i] != minnum:
Alist[i], Alist[minindex] = Alist[minindex], Alist[i]
if __name__ == '__main__':
l = [5, 3, 4, 7, 2]
select_sort(l)
print(l)
4.插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序
插入排序的组成:
插入算法把要排序的数组分成两部分：第一部分是有序的数字(这里可以默认数组第一个数字为有序的第一部分),第二部分为无序的数字(这里除了第一个数字以外剩余的数字可以认为是无序的第二部分)
def insert_sort(alist):
'''
自定义代码,插入排序
:param alist:
:return:
'''
n = len(alist)
for i in range(1, n):
# 外循环比较的轮数
for j in range(i, 0, -1):
# 内循环 每轮比较的总次数
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
else:
break
if __name__ == '__main__':
l = [5, 3, 44, -1, 44, 7, 2, 2, 2]
insert_sort(l)
print(l)
二分查找
二分查找又称折半查找，它是一种效率较高的查找方法
原理：将数组分为三部分，依次是中值前，中值，中值后
将要查找的值与中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回
第一步: 找到中值(取整数)
第二步: 要查找的数和中值比较
第三步: 若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回
'''
概述
是一种高效率的 查找类算法
要被查找的制表必须是有序的
实现方式:
递归版
非递归版
时间复杂度
最优:O(1)
最差:O(logn)
'''
def binary_search(my_list, item):
'''
递归版二分查找
:param my_list:
:param item:
:return:
'''
if not my_list:
return False
# 获取列表中值
n = len(my_list)
mid = n // 2
# 判断要查找的元素和中间位置的元素是否相等
if item == my_list[mid]:
return mid
elif item < my_list[mid]:
return binary_search(my_list[:mid], item)
else:
return mid + binary_search(my_list[mid + 1:], item) + 1
def binary_search2(my_list, item):
'''
非递归版二分查找
:param my_list:
:param item:
:return:
'''
if not my_list:
return False
n = len(my_list)
r = 0 #右指针
l = n - 1 # 左指针
while r < l:
mid = (r + l) // 2
if my_list[mid] == item:
return mid
elif my_list[mid] > item:
l = mid - 1
else:
r = mid + 1
if __name__ == '__main__':
my_list2 = [i for i in range(1000)]
print(binary_search(my_list2, 321))
print(binary_search2(my_list2, 213))
树:
树状结构介绍:
属于数据结构之非线性结构的一种
1. 有且只有一个根节点
2.每个节点都可以有1个父节点和任意个子节点
3.没有子节点的节点称之为:叶子节点
树的术语:
节点的度：一个节点含有的子节点的个数称为该节点的度
树的度：一棵树中，最大的节点的度称为树的度
叶节点或终端节点：度为零的节点
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的高度或深度：树中节点的最大层次
堂兄弟节点：父节点在同一层的节点互为堂兄弟
节点的祖先：从根到该节点所经分支上的所有节点
子孙：以某节点为根的子树中任一节点都称为该节点的子孙
森林：由m（m>=0）棵互不相交的树的集合称为森林
树的种类:
- 无序树: 树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树
- 有序树: 树中任意节点的子节点之间有顺序关系，这种树称为有序树
有序树:
- 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树-
- B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树
- 二叉树：每个节点最多含有两个子树的树称为二叉树
二叉树的种类:
- 完全二叉树:对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树
-
平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于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: 对于任意一棵二叉树，如果其叶结点数为N_0，而度数为2的结点总数为N_2 ，则N_0 = N_2+1
性质4: 最多有n个结点的完全二叉树的深度必为 log2(n+1)
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子
编号必为2i＋1 , 其父节点的编号必为i//2（i＝1 时为根,除外）
二叉树的遍历思路
- 广度优先遍历 0 1 2 3 4 5 6 7 8 9
- 深度优先遍历
- 先序遍历 0 1 3 7 8 4 9 2 5 6
- 中序遍历 7 3 8 1 9 4 0 5 2 6
- 后序遍历 7 8 3 9 4 1 5 6 2 0
二叉树及遍历代码实现
"""
树状结构介绍:
属于数据结构之非线性结构的一种
1. 有且只有一个根节点
2.每个节点都可以有1个父节点和任意个子节点
3.没有子节点的节点称之为:叶子节点
分类:
完全二叉树
满二叉树
不完全二叉树
常用的二叉树:
平衡二叉树
排序二叉树
存储方式:
更推荐使用链表的方式来存贮,每个节点有3部分组成,分别是:元素域(数值域) 左子树(地址域) 右子树(地址域)
"""
import random
class Node(object):
# 定义节点类
def __init__(self, item):
self.item = item
self.lchild = None # 左子树地址
self.rchild = None # 右子树地址
# 创建二叉树类
class BinaryTree(object):
def __init__(self, root=None):
self.root = root # 充当根节点
def add(self, item):
"""
添加元素
:param item:
:return:
"""
# 判断根节点是否存在
if not self.root:
self.root = Node(item)
return
# 找到新节点要添加的位置
queue = []
# 根节点添加到队列中
queue.append(self.root)
# 循环遍历队列,直至把新元素添加到合适的位置
while True:
# 获取队列的第一个元素
node = queue.pop(0)
# 判断当前节点的左子树是否存在
if not node.lchild:
# 如果当前节点的左子树不存在,就把新节点添加到这里
node.lchild = Node(item)
return True
else:
# 如果当前节点右子树存在,添加到队列中
queue.append(node.lchild)
if not node.rchild:
node.rchild = Node(item)
return True
else:
# 如果当前节点右子树存在,添加到队列中
queue.append(node.rchild)
def bread_travel(self):
"""
广度优先遍历
:return:
"""
# 判断根节点是否存在
if not self.root:
return
# 创建队列,记录所有的节点
queue = []
queue.append(self.root)
while queue:
# 获取队列的第一个元素
node = queue.pop(0)
# 打印该节点的内容
print(node.item, end='\t')
# 判断当前节点的左右子树是否存在,添加到队列中
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
def pre_order_travel(self, root):
"""
先序深度优先遍历
:return:
"""
if root:
# 先序
print(root.item, end=' ')
self.pre_order_travel(root.lchild)
self.pre_order_travel(root.rchild)
def in_order_travel(self,root):
"""
中序深度优先遍历
:return:
"""
if root:
self.in_order_travel(root.lchild)
print(root.item, end=' ')
self.in_order_travel(root.rchild)
def post_order_travel(self,root):
"""
后序深度优先遍历
:return:
"""
if root:
self.post_order_travel(root.lchild)
self.post_order_travel(root.rchild)
print(root.item, end=' ')
# 定义demo01 测试节点类和二叉树类
def demo01():
node1 = Node('abc')
print(f'节点的内容{node1.item}')
print(f'节点的右子树{node1.rchild}')
print(f'节点的左子树{node1.lchild}')
bt = BinaryTree(node1)
print(f'根节点{bt.root}')
print(f'根节点的内容{bt.root.item}')
print(f'根节点的右子树{bt.root.rchild}')
print(f'根节点的左子树{bt.root.lchild}')
n = 0
def nodec():
global n
node = Node(n)
n += 1
return node
def demo02():
bt = BinaryTree(nodec())
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.bread_travel()
def demo03():
bt = BinaryTree(nodec())
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.add(nodec().item)
bt.pre_order_travel(bt.root)
print()
bt.in_order_travel(bt.root)
print()
bt.post_order_travel(bt.root)
if __name__ == '__main__':
demo03()