什么是算法
就是一个计算的过程，解决问题的方法
用到知识点
递归
调用自身
有结束条件
下次执行相应的复杂度要减少
时间复杂度排序（按效率排序）
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
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！