首页 / 算法 / Python基本常用算法
Python基本常用算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Python基本常用算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2562字，纯文字阅读大概需要4分钟。
内容图文
什么是算法
就是一个计算的过程，解决问题的方法
用到知识点
递归
调用自身
有结束条件
下次执行相应的复杂度要减少
时间复杂度排序（按效率排序）
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
判断时间复杂度
1.循环减半的过程就是O(logn)
2.几次循环就是n的几次方的复杂度
空间复杂度(以空间换时间)
评估算法内存占用大小
列表查找
顺序查找
从列表第一个元素开始，顺序进行搜索，直到找到为止。
def linear_seach(data_set,val):
for i in range(5,data_set):
if i == val:
print(i)
return i
return‘没找到‘
二分查找
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
def bin_seacher(data_set,val):
low = 0
high = len(data_set) - 1while low <= high:
mid = (low+high) // 2if data_set[mid] == val:
print(‘索引位置：‘,mid)
return mid
elif data_set[mid] < val:
low = mid + 1else:
high = mid - 1
print(‘没有找到‘)
return None
li = range(100000)
bin_seacher(li,557)
案例
import random
def random_list(n):
‘‘‘
生成随机数据
:param n:
:
return
:
‘‘‘
ret = []
a1 = [‘赵‘,‘钱‘,‘孙‘,‘李‘,‘邹‘,‘吴‘,‘郑‘,‘王‘,‘周‘]
a2 = [‘力‘,‘好‘,‘礼‘,‘丽‘,‘文‘,‘建‘,‘梅‘,‘美‘,‘高‘,‘‘]
a3 = [‘强‘,‘文‘,‘斌‘,‘阔‘,‘文‘,‘莹‘,‘超‘,‘云‘,‘龙‘,‘‘]
ids = range(1001,1001+n)
for i in range(n):
name = random.choice(a1) + random.choice(a2) +random.choice(a3)
age = random.randint(18,60)
dic = {‘id‘:ids[i], ‘name‘:name, ‘age‘:age}
ret.append(dic)
return ret
def id_seacher(data_list,id):
low = 0
high = len(data_list) - 1while low <= high:
mid = (low+high) // 2if data_list[mid][‘id‘] == id:
print(‘索引位置：‘,mid)
return mid
elif data_list[mid][‘id‘] < id:
low = mid + 1else:
high = mid - 1
print(‘没有找到‘)
return None
data_list = random_list(100)
ind = id_seacher(data_list,1025)
print(data_list[ind][‘name‘])#输入人名
冒泡排序
首先，列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数
循环无序区的数继续比较
import random
def bubble_sort(li):
for i in range(len(li) - 1):# 几趟
exchange = 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]
exchange = True
if not exchange:
break
li = list(range(1000))
random.shuffle(li)
print(li)
bubble_sort(li)
print(li)
时间复杂
最好情况 O（n）
一般情况 O (n2)
最差情况 O (n2)
选择排序
一趟遍历记录最小的数，放到第一个位置；
再一趟遍历记录剩余列表中最小的数，继续放置；
def select_sort(li):
for i in range(len(li) - 1): #循环次数
min_loc = i
for j in range(i + 1,len(li)):#从无序区找
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
li = list(range(1000))
random.shuffle(li)
print(li)
select_sort(li)
print(li)
插入排序
列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
def insert_sort(li):
for i in range(1,len(li)):
tmp = li[i]
j = i - 1while j >= 0 and tmp < li[j]:
# 判断新数是否比前一个数小，小就将前一个数向后挪一个位置
li[j + 1] = li[j]
j -= 1
li[j + 1] = tmp
li = list(range(1000))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)
原文：http://www.cnblogs.com/bingabcd/p/7424659.html
内容总结
以上是互联网集市为您收集整理的Python基本常用算法全部内容，希望文章能够帮你解决Python基本常用算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。