几种常见的Python算法实现

开课吧开课吧锤锤2021-03-16 10:39

    众所周知,Python目前越来越火,学习Python的小伙伴也越来越多。无论你是初学者想要学习Python入门,还是将Python用于Web开发,或是将Python用于脚本和自动化管理等,都要认真开始好好学习基础,几天就为大家讲解一下几种常见的Python算法实现。

py

    1、选择排序

    选择排序是一种简单直观的排序算法。它的原理是这样:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的后面,以此类推,直到所有元素均排序完毕。算法实现如下:

    #找到最小的元素defFindSmall(list):min=list[0]foriinrange(len(list)):iflist[i]

    2、快速排序

    快速排序的运行速度快于选择排序,它的工作原理是这样:设要排序的数组是N,首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。可以使用python用递归式的方法来解决这个问题:

    defQuick_Sort(list):iflen(list)<2:returnlistelse:temp=list[0]less=[iforiinlist[1:]ifi<=temp]more=[iforiinlist[1:]ifi>temp]returnQuick_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步,而二分查找法则最多只需lon2n步。下面用python来实现该算法:

    defItem_Search(list,item):low=0high=len(list)-1whilelow<=high:middle=(low+high)//2print(list[middle])iflist[middle]>item:high=middle-1eliflist[middle]

    4、广度优先搜索

    广度优先搜索是一种图算法,图由节点和边组成,一个节点可能与多个节点连接,这些节点称为邻居。广度优先搜索算法可以解决两类问题:第一类是从节点A出发,有没有前往节点B的路径;第二类问题是从节点A出发,前往B节点的哪条路径最短。使用广度优先搜索算法的前提是图的边没有权值,即该算法只用于非加权图中,如果图的边有权值的话就应使用狄克斯特拉算法来查找最短路径。举个例子,假如你认识alice、bob、claire,bob认识anuj、peggy,alice认识peggy,claire认识tom、jonny,你需要在最短的路径内找到通过认识的人找到tom,那么算法实现如下:

    #使用字典构建图graph={}graph["you"]=["Alice

    以上就是几种常见的Python算法实现的全部内容,如果想了解更多的Python教程尽在开课吧广场Python教程频道!

有用
分享