算法篇
- 递归：斐波那契
必须有结束条件
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 ra����,����nge(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