Python几种常见算法汇总

1、选择排序

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

#找到最小的元素def FindSmall(list):
  min=list[0]  for i in range(len(list)):    if list[i]<min:
      min=list[i]  return min    

#选择排序def Select_Sort(list):
  newArr=[]  for i in range(len(list)):
    minValue=FindSmall(list)
    newArr.append(minValue)
    list.remove(minValue)  return newArr

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]<item:
      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() #包含该箱子包含的所有未包含的水果

  #循环迭代每个箱子,并确定它是否为最佳箱子
  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几种常见算法汇总的详细内容,更多关于Python算法汇总的资料请关注我们其它相关文章!

(0)

相关推荐

  • python语言中有算法吗

    了解算法之前,我们先看一下什么是算法 定义:算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出.如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题.不同的算法可能用不同的时间.空间或效率来完成同样的任务.一个算法的优劣可以用空间复杂度与时间复杂度来衡量. python中的常见算法 冒泡排序 效率:O(n2) 原理: 比较相邻的元素,如果

  • python 的topk算法实例

    我就废话不多说了,还是直接看代码吧! #! conding:utf-8 def quick_index(array, start, end): left, right = start, end key = array[left] while left < right: while left < right and array[right] > key: right -= 1 array[left] = array[right] while left < right and arra

  • Python如何实现的二分查找算法

    先来看个用Python实现的二分查找算法实例 import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else: print mid return mid print -1 return -1 if _

  • Python几种常见算法汇总

    1.选择排序 选择排序是一种简单直观的排序算法.它的原理是这样:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的后面,以此类推,直到所有元素均排序完毕.算法实现如下: #找到最小的元素def FindSmall(list): min=list[0] for i in range(len(list)): if list[i]<min: min=list[i] return min #选择排序def Select_

  • 一文带你了解Python 四种常见基础爬虫方法介绍

    一.Urllib方法 Urllib是python内置的HTTP请求库 import urllib.request #1.定位抓取的url url='http://www.baidu.com/' #2.向目标url发送请求 response=urllib.request.urlopen(url) #3.读取数据 data=response.read() # print(data) #打印出来的数据有ASCII码 print(data.decode('utf-8')) #decode将相应编码格式的

  • Python 5种常见字符串去除空格操作的方法

    目录 1:strip()方法 2:lstrip()方法 3:rstrip()方法 4:replace()方法 5: join()方法+split()方法 1:strip()方法 去除字符串开头或者结尾的空格 >>> a = " a b c " >>> a.strip() 'a b c' 2:lstrip()方法 去除字符串开头的空格 >>> a = " a b c " >>> a.lstrip(

  • Python单体模式的几种常见实现方法详解

    本文实例讲述了Python单体模式的几种常见实现方法.分享给大家供大家参考,具体如下: 这里python实现的单体模式,参考了:https://stackoverflow.com/questions/1363839/python-singleton-object-instantiation/1363852#1363852 一.修改父类的 __dict__ class Borg: _shared_state = {} def __init__(self): self.__dict__ = self

  • Python实现自定义函数的5种常见形式分析

    本文实例讲述了Python自定义函数的5种常见形式.分享给大家供大家参考,具体如下: Python自定义函数是以def开头,空一格之后是这个自定义函数的名称,名称后面是一对括号,括号里放置形参列表,结束括号后面一定要有冒号":",函数的执行体程序代码也要有适当的缩排.Python自定义函数的通用语法是: def   函数名称(形参列表): 执行体程序代码 Python自定义函数的5种常见形式: 1.标准自定义函数: -----形参列表是标准的tuple数据类型 >>>

  • Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

  • java性能优化四种常见垃圾收集器汇总

    目录 前言 常见的垃圾回收器和算法 serial 串行垃圾收集器 Parallel 多线程垃圾收集器 CMS 收集器 G1 收集器 显式垃圾收集 前言 本篇文章我们来具体看看如何选择合适的垃圾收集器.每种垃圾收集器都有其不同的算法实现和步骤,下面我们简单描述下我们常见的四种垃圾收集器的算法过程,感兴趣的同学们最好先看下以下的两篇文章去增加理解.分别介绍了一些垃圾回收的基本概念,和各种垃圾回收器回收的过程,内容重复,本章不会在去单独讲解一遍.所以本章做一些归纳总结. JVM GC 垃圾收集梳理总结

  • 用Python解析XML的几种常见方法的介绍

    一.简介 XML(eXtensible Markup Language)指可扩展标记语言,被设计用来传输和存储数据,已经日趋成为当前许多新生技术的核心,在不同的领域都有着不同的应用.它是web发展到一定阶段的必然产物,既具有SGML的核心特征,又有着HTML的简单特性,还具有明确和结构良好等许多新的特性.         python解析XML常见的有三种方法:一是xml.dom.*模块,它是W3C DOM API的实现,若需要处理DOM API则该模块很适合,注意xml.dom包里面有许多模块

  • Python爬虫定时计划任务的几种常见方法(推荐)

    记得以前的Windows任务定时是可以正常使用的,今天试了下,发现不能正常使用了,任务计划总是挂起.接下来记录下Python爬虫定时任务的几种解决方法. 1.方法一.while True 首先最容易的是while true死循环挂起,不废话,直接上代码: import os import time import sys from datetime import datetime, timedelta def One_Plan(): # 设置启动周期 Second_update_time = 24

  • python如何实现常用的五种排序算法详解

    一.冒泡排序 原理: 比较相邻的元素.如果第一个比第二个大就交换他们两个 每一对相邻元素做同样的工作,直到结尾最后一对 每个元素都重复以上步骤,除了最后一个 第一步: 将乱序中的最大值找出,逐一移到序列最后的位置 alist = [3, 5, 9, 2, 1, 7, 8, 6, 4] def bubble_sort(alist): # 找最大值的方式是通过对列表中的元素进行两两比较,值大的元素逐步向后移动 # 序列中有n个元素,两两比较的话,需要比较n-1次 for i in range(len

随机推荐