python 算法 一
程序员文章站
2022-03-10 11:38:19
二分查找算法 def list_search(l,v): left = 0 right = len(l) -1 while left <= right: mid = (left + right) // 2 if l[mid] == v: return mid elif l[mid] < v: lef ......
- 二分查找算法
def list_search(l,v):
left = 0
right = len(l) -1
while left <= right:
mid = (left + right) // 2
if l[mid] == v:
return mid
elif l[mid] < v:
left = mid +1
else:
right = mid -1
else:
return none
l = list(range(100))
s = list_search(l,50)
print(s)
个人总结:查找的值所在的数据类型中以数据中心的值分割,如果等于则找到,如果小于中心值,查找的值在右部分,重新定义左边最后一个值,就是中心值加一,大于,值在左,重新定义右边值,减一,直到找到,否则返回none。
- 排序算法
1.冒泡排序:
import random
def bubble_sort(l):
for i in range(len(l)-1):
exchange = false
for x in range(len(l)-i-1):
if l[x] > l[x+1]:
l[x], l[x+1] = l[x+1],l[x]
exchange = true
if not exchange:
return
l = [random.randint(1,10) for i in range(10)]
s = bubble_sort(l)
print(l)
个人总结:比较,i比较几次,(索引0-9,长度是十个所以减一,不然多循环一次),减去比较完的次数,在减一,比较大于正序,调换,小于反序。定义一个bool,如果走了调换位置,就设置为true,没有走的话,就证明已经排序完成了,就直接返回。
2.选择排序
def select_sort(l):
for i in range(len(l)-1):
min = i
for x in range(i,len(l)):
if l[x] < l[min]:
min = x
l[i],l[min] = l[min],l[i]
l = [random.randint(1,10) for i in range(10)]
select_sort(l)
print(l)
循环一个然后和后面的值循环比较,比我小,换你来当最小的,换位,大,直接换。
3.插入排序
def insert_sort(l):
for i in range(1,len(l)):
tmp = l[i]
j = i-1 #后面的值
while j >=0 and l[j] > tmp:
l[j+1] = l[j] #把j的位置向前面移动一位
j -= 1 #和后面的继续比较
l[j+1] = tmp #循环结束条件不成立,索引负数,比j大的直接插
l = [1,6,5,8,9,7,3,4,2]
insert_sort(l)
print(l)
#从第一个值开始比较,第0个是比较对象
快排
def partition(l,left,right):
tmp = l[left]
while left < right:
while left < right and l[right] > tmp :
right -=1
l[left] = l[right]
while left < right and l[left] < tmp :
left += 1
l[right] = l[left]
l[left] = tmp
return left
def quick_sort(l,left,right):
if left < right:
mid = partition(l,left,right)
#递归
quick_sort(l,left,mid-1) #左边在重新快排
quick_sort(l,mid+1,right) #右边在重新快排
l = [6, 3, 4, 8, 5, 2, 9, 1,17,7,10,11]
quick_sort(l,0,len(l)-1)
print(l)
循环左边之和右边的值,拿第一个值,和最右边的值比较比tmp大向左边就继续找,比tmp小就把它换到左边,左边的相反操作,最后把tmp放到中间的位置,然后把tmp返回。