python编程的50种基础算法_Python⼊门教程：⼏种常见的
Python算法实现
今天跟⼤家总结的Python学习教程关于Python算法的实现，上次催我更算法的伙伴可以粗来了！
1、选择排序
选择排序是⼀种简单直观的排序算法。它的原理是这样：⾸先在未排序序列中到最⼩（⼤）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻最⼩（⼤）元素，然后放到已排序序列的后⾯，以此类推，直到所有元素均排序完毕。算法实现如下：
#到最⼩的元素def FindSmall(list):
min=list[0] for i in range(len(list)): if list[i]
min=list[i] return min
#选择排序def Select_Sort(list):
newArr=[] for i in range(len(list)):
minValue=FindSmall(list)
newArr.append(minValue)
testArr=[11,22,33,21,123]print(Select_Sort(testArr))
2、快速排序
快速排序的运⾏速度快于选择排序，它的⼯作原理是这样：设要排序的数组是N，⾸先任意选取⼀个数据（通常选⽤数组的第⼀个数）作为关键数据，然后将所有⽐它⼩的数都放到它前⾯，所有⽐它⼤的数都放到它后⾯，这个过程称为⼀趟快速排序。可以使⽤python⽤递归式的⽅法来解决这个问题：
def Quick_Sort(list): if len(list)<2: return list else:
temp=list[0]
less=[i for i in list[1:] if i<=temp]
more=[i for i in list[1:] if i>temp] return Quick_Sort(less)+[temp]+Quick_Sort(more)
testArr= [13,44,53,24,876,2]print(Quick_Sort(testArr))
3、⼆分查
⼆分查的输⼊是⼀个有序的列表，如果要查的元素包含在⼀个有序列表中，⼆分查可以返回其位置。打个⽐⽅来说明⼆分查的原理：⽐如我随便想了个范围在1~100以内的整数，由你来猜，以最少的次数来猜出这个数字，你每次猜完给出个数字，我会回复⼤了或⼩了，第⼀种⽅法是你从1开始依次往后猜，那如果我想的数字是100，那么你就要猜100次；第⼆种⽅法是从50开始，如果我说⼩了，那你就猜75，就这样依次排除掉⼀半的剩余数字，这就是⼆分查法。可以看出⼆分查法更加快速。对于包含n个元素的有序列表，⽤简单查最多需要n步，⽽⼆分查法则最多只需lon2 n步。下⾯⽤python来实现该算法：
def Item_Search(list,item):
low=0
high=len(list)-1 while low<=high:
middle=(low+high)//2 print(list[middle]) if list[middle]>item:
high=middle-1 elif list[middle]
low=middle+1 else: return middle return None
test_list=[1,3,5,7,9,11,13,15,17,19,21]
Item_Search(test_list,11)
4、⼴度优先搜索
⼴度优先搜索是⼀种图算法，图由节点和边组成，⼀个节点可能与多个节点连接，这些节点称为邻居。⼴度优先搜索算法可以解决两类问题：第⼀类是从节点A出发，有没有前往节点B的路径；第⼆类问题是从节点A出发，前往B节点的哪条路径最短。使⽤⼴度优先搜索算法的前提是图的边没有权值，即该算法只⽤于⾮加权图中，如果图的边有权值的话就应使⽤狄克斯特拉算法来查最短路径。举个例⼦，假如你认识alice、bob、claire，bob认识anuj、peggy，alice认识peggy，claire认识tom、jonny，你需要在最短的路径内到通过认识的⼈到tom，那么算法实现如下：
#使⽤字典构建图graph={}
graph["you"]=["Alice","Bob","Claire"]
graph["Bob"]=["Anuj","Peggy"]
graph["Alice"]=["Peggy"]
graph["Claire"]=["Tom","Jonny"]
graph["Anuj"]=[]
graph["Peggy"]=[]
graph["Tom"]=[]
graph["Jonny"]=[]from collections import deque#简单的判断⽅法def person_is_seller(name): return name=='Tom'def
Search(name):
searched=[] #⽤于记录检查过的⼈，防⽌进⼊死循环
search_queue=deque() #创建队列
search_queue+=graph[name] while search_queue:
person=search_queue.popleft() if not person in searched: #仅当这个⼈没检查过时才检查
if person_is_seller(person): print("the seller is {0}".format(person)) return True else:
search_queue+=graph[person]
searched.append(person) #将这个⼈标记为检查过
return Falseprint(Search("you"))
5、贪婪算法
贪婪算法，⼜名贪⼼算法，对于没有快速算法的问题（NP完全问题），就只能选择近似算法，贪婪算法寻局部最优解，并企图以这种⽅式获得全局最优解，它易于实现、运⾏速度快，是⼀种不错的近似算法。假如你是个⼩偷，商店⾥有很多箱⼦，箱⼦⾥有各种⽔果，有些箱⼦⾥有3种⽔果，有些箱⼦有2种...，你想尝到所有种类的⽔果，但你⼀个⼈⼒⽓有限，因此你必须尽量搬⾛最少的箱⼦，那么，算法实现如下：
fruits=set(["苹果","⾹蕉","梨⼦","西⽠","草莓","橘⼦","荔枝","榴莲"])
#箱⼦以及包含的⽔果box={}
box["b1"]=set(["苹果","⾹蕉","西⽠"])
box["b2"]=set(["草莓","橘⼦","榴莲"])
box["b3"]=set(["梨⼦","荔枝","草莓"])
box["b4"]=set(["⾹蕉","橘⼦"])
box["b5"]=set(["梨⼦","榴莲"])
final_boxs=set() #最终选择的箱⼦#直到fruits为空while fruits:
best_box=None #包含了最多的未包含⽔果的箱⼦
fruits_covered=set() #包含该箱⼦包含的所有未包含的⽔果
#循环迭代每个箱⼦，并确定它是否为最佳箱⼦python新手编程100例
for boxItem,fruitItem in box.items():
covered=fruits & fruitItem #计算交集
if len(covered)>len(fruits_covered):
best_box=boxItem
fruits_covered=covered
fruits-=fruits_covered
final_boxs.add(best_box)
print(final_boxs)
伙伴们有补充的地⽅可以留⾔哈！感谢⼤家⼀致以来的⽀持！更多的Python⼊门教程会继续跟⼤家更新！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。