算法与数据结构
算法
算法概念
算法(Algorithm):一个计算过程,解决问题的方法。
Niklaus Wirth说过:“程序=数据结构+算法”
时间复杂度
时间复杂度:用来评估算法运行效率的一个式子。一般来说,时间复杂度高的算法比复杂度低的算法慢
常见的时间复杂度:O(1)<O(logn)<O(n)
快速判断算法复杂度(适用于绝大多数简单情况):
- 确定问题规模n
- 循环减半过程->logn
- k层关于n的循环->n**k
复杂情况:根据算法执行过程判断
空间复杂度
空间复杂度:用来评估算法内存占用大小的式子
空间复杂度的表示方式与实践复杂度完全一样:
- 算法使用了几个变量:O(1)
- 算法使用了长度为n的一维列表:O(n)
- 算法使用了m行n列的二维列表:O(mn)
“空间换时间”:时间比空间重要,分布式技术就是这个原理
递归
递归的两个特点:
- 调用自身
- 结束条件
了解了以上概念,我们就开始真正的学习算法了!
查找
查找:在一些数据元素中,通过一定的方法找出与给定关键字相同的数据元素的过程
列表查找(线性表查找):从列表中查找指定元素
输入:列表、待查找元素;输出:元素下标(未找到元素时一般返回None或-1)
内置列表查找函数:index()
顺序查找
顺序查找:也叫线性查找,从列表第一个元素开始,顺序进行搜索,直到找到元素或搜索到列表最后一个元素为止
#线性查找
def linear_search(li,value):
for ind,val in enumerate(li):
if val == value:
return ind
else:return None
时间复杂度:O(n)
二分查找
二分查找:又叫折半查找,从有序列表的初始候选区li[0:n]开始,通过对 待查找 的值与候选区中间值的比较,可以使候选区减少一般
#二分查找
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:
left = mid + 1
else:
right = mid -1
else:
return None
时间复杂度:O(logn)
排序
排序:将一组“无序”的记录序列调整为“有序”的记录序列
列表排序:将无序列表变为有序列表
输入:列表;输出:有序列表
升序与降序
内置排序函数:sort()
冒泡排序
列表每两个相邻的数,如果前面比后面大,则交换这两个数
一趟排序完成后,则无序区减少一个数,有序区增加一个数
def bubble_sort(li):
for i in range(len(li)-1): #第i趟,总共需要排n-1趟
exchage = 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]
exchage = True
print(li)
if not exchage:
return
时间复杂度:O(n**2)
选择排序
一趟排序记录最小的数,放到第一个位置
再一趟排序记录列表无序区最小的数,放到第二个位置
算法关键点:有序区和无序区、无序区最小数的位置
def select_sort(li):
for i in range(len(li)-1):#i是第几趟
min_loc = i #初始化最小值的下标
for j in range(i+1,len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[min_loc],li[i] = li[i],li[min_loc]
return li
时间复杂度:O(n**2)
插入排序
初始时手里(有序区)只有一张牌
每次(从无序区)摸一张牌,插入到手里已有牌的正确位置
def insert_sort(li):
for i in range(1,len(li)): #表示摸到的牌的下标
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 #插入
return li
时间复杂度:O(n**2)
快速排序
取一个元素p(第一个元素)使元素p归位–到他该到的位置
列表被p分成两部分,左边都比p小,右边都比p大
递归左右两边完成排序
def partition(li,left,right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: #从右边找比tmp小的数,这里再加一个判断left<right是为了当右边全比tmp大时,可以直接跳出while循环,不再执行下面的向右走循环
right -= 1 #往左走一步
li[left] = li[right] #把右边的值写到左边的空位上
while left < right and li[left] <= tmp: #从左边找比tmp大的数
left += 1 #往右走一步
li[right] = li[left] #把左边的值写到左边的空位上
li[left] = tmp #把tmp归位
return left
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)
时间复杂度:O(nlogn)
堆排序
堆排序前传–树与二叉树
树是一种可以递归定义的数据结构,比如:目录结构
树是由n个节点组成的集合:
- 如果n=0,那这是一棵空树
- 如果n>0,那存在1个节点作为树的根节点,其他节点可以分为m个集合,每个集合本身又是一棵树
树的度:节点往下分几个叉
二叉树:度不超过2的树
每个节点最多有两个孩子节点
两个孩子节点被区分为左孩子节点和右孩子节点
满二叉树:一个二叉树,如果每一层的节点数都达到最大值,则这个二叉树就是满二叉树
完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的节点都集中在该层最左边的若干位置的二叉树
二叉树的存储方式(表示方式):
- 链式存储方式
- 顺序存储方式
堆排序
堆:一种特殊的完全二叉树结构
大根堆:一棵完全二叉树,满足任一节点都比其孩子节点大
小根堆:一棵完全二叉树,满足任一节点都比其孩子节点小
堆的向下调整:假设:节点的左右子树都是堆,但自身不是堆。当根节点的左右子树都是堆时,可以通过一次向下的调整来将其换成一个堆
如何进行堆排序:
- 建立堆。
- 得到堆顶元素。
- 去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整重新使堆有序。
- 堆顶元素为第二大元素。
- 重复步骤3、4,直到堆空。
#向下调整过程
def sift(li,low,high):
"""
:param li: 列表
:param low: 堆的根节点位置
:param right: 堆的最后一个元素的位置
:return:
"""
i = low#i最开始指向根节点
j = 2 * i + 1#j开始是左孩子
tmp = li[low]#把堆顶存起来
while j <= high:#如果右孩子有并且比较大
if j+1 <=high and li[j+1] > li[j]:
j = j+1 #j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j #往下看一层
j = 2*i + 1
else: #tmp更大,把tmp放到i的位置上
li[i] = tmp#把tmp放到某一级领导的位置
break
else:
li[i] = tmp#把tmp放到叶子节点上的位置
#实现堆排序
def heap_sort(li):
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
时间复杂度:O(nlogn)
堆排序–内置模块
Python内置模块–heapq
常用函数:
- heapify(x) #建堆
- heappush(heap,item)
- heappop(heap)
堆排序–topk问题
现在有n个数,设计算法得到前k大的数(k<n)
解决思路:
取列表前k个元素建立一个小根堆,堆顶就是目前第k大的数
依次向后遍历原列表,对于列表中的元素,如果小于堆顶,则忽略该元素;如果大于堆顶,则将堆顶更换为该元素,并且对堆进行一次调整
def sift(li,low,high):
i = low
j = 2*i + 1
tmp = li[low]
while j <= high:
if j + 1 <= high and li[j+1] < li[j]:
j = j+1
if li[j] < tmp:
li[i] = li[j]
i = j
j = 2*i + 1
else:
break
li[i] = tmp
def topk(li,k):
# 1、建堆
heap = li[0:k]
for i in range((k-2)//2,-1,-1):
sift(heap,i,k-1)
#2、遍历
for i in range(k,len(li)-1):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap,0,k-1)
#3、出数
for i in range(k-1,-1,-1):
heap[0], heap[i] = heap[i], heap[0]
sift(li,0,i-1)
return heap
时间复杂度:O(nlogk)
归并排序
分解:将列表约分越小,直至分成一个元素
终止条件:一个元素是有序的
合并:将两个有序列表归并,列表越来越大
def merge(li,low,mid,high):
i = low
j = mid + 1
ltmp = []
while i<=mid and j<=high:#只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
#while执行完,肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
def merge_sort(li,low,high):
if low < high:#至少有两个元素
mid = (low + high) // 2
merge_sort(li,low,mid)
merge_sort(li,mid,high)
merge(li,low,mid,high)
时间复杂度:O(nlogn)
希尔排序
希尔排序是一种分组插入排序算法
首先取一个整数d1=n/2,将元素分为d1个组,每组相邻量元素之间距离为d1,在各组内进行直接插入排序
取第二个整数d2=d1/2,重复上诉分组排序过程,直到di=1,即所有元素在同一组内进行直接插入排序
希尔排序每趟并不使某些元素有序,而是整体数据越来越接近有序;最后一趟排序使得所有数据有序
def insert_sort_gap(li,gap):
for i in range(gap,len(li)):#表示摸到的牌的下标
tmp = li[i]
j = i-gap #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:#右移的条件
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp#插入
def shell_sort(li):
d = len(li) // 2
while d >= 1:
insert_sort_gap(li,d)
d //= 2
计数排序
对列表进行排序,已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法
建立一个列表,下标为0~100,值为当前下标在列表中出现的次数
def count_sort(li,max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind,val in enumerate(count):
for i in range(li):
li.append(ind)
在计数排序中,如果元素的范围比较大(比如在1到1亿之间),如何改造算法?桶排序是一个解决方法
桶排序:首先将元素分在不同的桶中,再对每个桶中的元素排序
比如最大的数是10000,第一个桶就是0100,第二个桶就是101200 …
def bucket_sort(li,n=100,max_num=10000):
buckets = [[] for _ in range(n)]#创建桶
for val in li:
i = min(val // (max_num // n),n-1)#i表示val放到几号桶中
buckets[i].append(val) #把val加到桶里
#保持桶内的顺序
for j in range(len(buckets[i])-1,0,-1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j],buckets[i][j-1] = buckets[i][j-1],buckets[i][j]
else:
break
sorted_li = []
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
基数排序
多关键字排序:假如现在有一个员工表,要求按照年龄排序,年龄相同的员工按照工资排序
先按照年龄进行排序,再按照薪资进行稳定的排序
数字的排序也可以看作是多关键字排序:比如两位数的数字进行比较,先比较十位,再比较个位 …
但是在此算法中,我们是先从最后一位开始排序,再一次排序前一位
def radix_sort(li):
max_num = max(li)#最大值 9->1位数,99->2位数,999->3位数,1000->4位数
it = 0 #位数标志符
while 10 ** it <= max_num:
buckets = [[] for _ in range(10)]
for val in li:
#987 it=0 987%10->7; it=1 987//10->98 98%10->8; it=2 987//100->9
digit = (val // 10 ** it) % 10
buckets[digit].append(val)
#分桶完成
li.clear()
for buc in buckets:
# 把数重新写回li
li.extend(buc)
it += 1
时间复杂度:O(max_num*n)
数据结构
数据结构概念
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成
简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中
比如:列表、集合与字典等都是一种数据结构
Niklaus Wirth说过:“程序=数据结构+算法”
数据结构分类
数据结构按照其逻辑结构可分为线性结构、树结构、图结构
- 线性结构:数据结构中的元素存在一对一的相互关系
- 树结构:数据结构中的元素存在一对多的相互关系
- 图结构:数据结构中的元素存在多对多的相互关系
列表
列表(其他语言称数组)是一种基本数据类型
列表的元素类型可以不同
python存列表存的不是值,而是地址
栈
栈的概念
栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除操作的列表
栈的特点:后进先出LIFO(last-in,first-out)
栈的概念:栈顶、栈底
栈的基本操作:
- 进栈(压栈):push
- 出栈:pop
- 取栈顶:gettop
栈的实现
使用一般的列表结构即可实现栈:
- 进栈:li.append
- 出栈:li.pop
- 取栈顶:li[-1]
class Stack:
def __init__(self):
self.stack = []
def push(self,element):
self.stack.append(element)
def pop(self):
return self.stack.pop()
def get_top(self):
if len(self.stack) > 0:
return self.stack[-1]
else:
return None
def isEmpty(self):
return len(self.stack) == 0
队列
队列的概念
队列(Queue)是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除
进行插入的一端称为队尾(rear),插入动作称为进队或入队
进行删除的一端称为对头(front),删除动作称为出队
队列的性质:先进先出FIFO(First-in,First-out)
队列的实现
环形队列:当前对位指针front==MaxSize+1时,再前进一个位置就自动到0
- 队首指针前进1:front=(front+1)%MaxSize
- 队尾指针前进1:rear=(rear+1)%MaxSize
- 队空条件:rear==front
- 队满条件:(rear+1)%MaxSize==front
class Queue:
def __init__(self,size=100):
self.queue = [0 for _ in range(size)]
self.size = size
self.rear = 0 #队尾指针
self.front = 0 #队首指针
def push(self,element):
if not self.is_filled():
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is Filled")
def pop(self):
if not self.is_empty():
self.front = (self.front + 1) % self.size
return self.queue[self.front]
else:
raise IndexError("Queue is Empty")
#判断队空
def is_empty(self):
return self.rear == self.front
#判断队满
def is_filled(self):
return (self.rear + 1) % self.size == self.front
双向队列
双向队列的两端都支持进队和出队操作
双向队列的基本操作:
- 队首进队
- 队首出队
- 队尾进队
- 队尾出队
队列的内置模块
使用方法:from collections import deque:
- 创建队列:queue = deque()
- 进队:append()
- 出队:popleft()
- 双向队列队首进队:appendleft()
- 双向队列队尾出队:pop()
- 标题: 算法与数据结构
- 作者: 宣胤
- 创建于: 2023-06-08 16:39:36
- 更新于: 2023-06-12 18:56:08
- 链接: http://xuanyin02.github.io/2023/060851507.html
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。