算法篇
- 递归:斐波那契
必须有结束条件
python默认层数998
斐波那契数列规律:0,1,1,2,3,5,8……
台阶问题:走1,走2,n阶有几种方案:fib = lambda n:n if n <= 2 else fib(n-1) + fib(n-2)
台阶升级:走1,走2,走n: fib = lambda n:n if n<=2 else 2* fib(n-1)
def feibo(n):
"""计算几个feibo数"""
if n ==1:return 0
if n == 2: return 1
return feibo(n-1) + feibo(n-2)
- 二分查找:必须是有序的 O(logn)
找到中间值,让待找值与中间值比,然后去两边找,条件就是左边的索引小于右边
def second_select(li, vlue):
low = 0
high = len(li) -1
while low <=high:
mid = (low + high)//2
if li[mid] == vlue:
return mid
elif li[mid] > vlue:
high = mid -1
elif li[mid] < vlue:
low = mid +
else:
return "没有该值"
- 选择排序On^2
分有序无序,每次都从无序里获取最小的值放到有序最后一位的后面,直到无序区为空
def select_sort(li):
for i in range(len(li)-1):
min_tmp = i
for j in range(i+1, len(li)):
if li[j] < li[min_tmp]
min_tmp = j
if min_tmp != j:
li[i], li[min_tmp] = li[min_tmp] ,li[i]
- 插入排序 On^2
分有序和无序,先从无序开始选一个数,放入有序区,然后从无序区拿元素与有序区元素依次比较,如果小于有序区,就换位置,如果大就放在它后面,依次进行
def insert_sort(li):
for i in range(1, len(li)): # 先拿到了0号元素,这里时无序区开始拿
tmp = li[i] # 获取到的第一个数
j = i -1 # 为有序区的索引
while j >=0 and tmp < li[j]:
li [j+1] = li[j] # 换位置
j = j -1 # 有序区继续比较
li[j+1] = tmp
- 冒泡
从一个列表开始元素依次开始比较相邻的数,如果后面的大于前面的,不做改变,指针向后移动,如果后面的数小于前面的,将他们的位置更换,依次到最后,就实现了最大的数字放在了最后,类似水泡冒上来
def mao_sort(li):
for i in range(len(li) -1): # 趟数
flag = 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]
flag = True
if not flag:
return
- 快排On^2
找到中间值,将列表分为两部分,左边的元素都比中间值小,右边的元素都比中间值大,然后两部分也这样递归的运行
def quick_sort(li, left,right):
if left < right:
mid = partition(li, left, right)
quick_sort(li, left, mid-1)
quick_sort(li, mid+1)
def partition(li, left,right):
tmp = li[left] # 先假设第一个值是中间的那个
while left < right:
while left < right and li[right] >= tmp:
right -=1
li[left] = li[right]
while left < right and li[right] <= tmp:
left+-=1
li[right]= li[left]
li[left] = tmp
return left
- 归并O(nlogn)
通过不断的分解无序列表,直到成一个元素时就有序了,最后分成两个有序的列表,然后将两个有序列表进行归并,一步步递归合成一个有序的大列表
归并排序采用分而治之的原理:
一、将一个序列从中间位置分成两个序列;
二、在将这两个子序列按照第一步继续二分下去;
三、直到所有子序列的长度都为1,也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。
def merge(li, low, mid, high):
li_tmp = []
i = low
j = mid + 1
while i <= mid and j <= high:
if li[i] <= li[j]:
li_tmp.append(li[i])
i += 1
else:
li_tmp.append(li[j])
j += 1
while i <= mid:
li_tmp.append(li[i])
i += 1
while j <= high:
li_tmp.append(li[j])
j += 1
for i in range(len(li_tmp)):
li[i+low] = li_tmp[i]
def _merge_sort(li, low, high):
if low < high: # 2个元素及以上
mid = (low + high) // 2
_merge_sort(li, low, mid)
_merge_sort(li, mid+1, high)
#print(li[low:mid+1], li[mid+1:high+1])
merge(li, low, mid, high)
#print(li[low:high + 1])
# 两个列表的写法
def merge_two(li1, li2):
li = []
i = 0
j = 0
while i < len(li1) and j < len(li2):
if li1[i] <= li2[j]:
li.append(li1[i])
i += 1
else:
li.append(li2[j])
j += 1
while i < len(li1):
li.append(li1[i])
i += 1
while j < len(li2):
li.append(li2[j])
j += 1
return li