算法-----python实现

斐波那契数列

def f(n):if n == 1:return 1elif n == 2:return 1else:return f(n-1)+f(n-2)print(f(8))

用普通函数实现斐波那契数列：

def f(n):li = [0,1,1]if n <=2:return li[n]for i in range(3,n+1):li.append(li[-1]+li[-2])return li[n]print(f(8))

常见的时间复杂度（按照效率排序）

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

递归实例：汉诺塔问题

def hanoi(n,A,B,C):if n > 0:hanoi(n-1,A,C,B)print("%s->%s"%(A,C))hanoi(n-1,B,A,C)hanoi(4,"A","B","C")

二分查找

def binary_search(li, val):low = 0high = len(li) - 1while low <= high:mid = (low + high) // 2if li[mid] < val:low = mid + 1elif li[mid] > val:high = mid -1else:return midreturn None

冒泡排序

import randomdef bubble_sort(li):for i in range(len(li)-1):  # i表示第i趟,共n-1趟# 第i趟 无序区范围 0~n-i-1for j in range(len(li)-i-1):if li[j] > li[j+1]:li[j],li[j+1] = li[j+1],li[j]print(li)li = [8,5,7,9,4,2,6,1,3]
bubble_sort(li)

冒泡排序------优化

@cal_time
def bubble_sort_2(li):for i in range(len(li)-1):exchange = Falsefor j in range(len(li)-1):if li[j] > li[j+1]:li[j],li[j+1] = li[j+1],li[j]exchange = Trueif not exchange:returnli=list(range(10000))
random.shuffle(li)
bubble_sort_2(li)

冒泡排序最好时间复杂度是O(n),最坏时间复杂度是O(n2)

选择排序：

import random
from cal_time import *# 找到最小数的位置
def find_min_pos(li):min_pos = 0for i in range(1,len(li)):if li[i] < li[min_pos]:min_pos = ireturn min_pos@cal_time
def select_sort(li):for i in range(len(li)-1):min_pos = ifor j in range(i+1,len(li)):if li[j] < li[min_pos]:min_pos = jli[i],li[min_pos] = li[min_pos],li[i]li = list(range(10000))
select_sort(li)

选择排序没有最好排序，最坏时间复杂度是O(n2)

插入排序：

import random
from cal_time import *
@cal_time
def insert_sort(li):for i in range(1,len(li)):# i 表示趟数 还表示摸到牌的位置j = i-1tmp = li[i]while j>=0  and li[j] > tmp:# 两个终止条件： 1. j==-1 2. j位置的值小于等于tmpli[j+1] = li[j]j -=1li[j+1] = tmpli = list(range(10000))
random.shuffle(li)
insert_sort(li)

插入排序的最好情况也是O(n),最坏时间复杂度是O(n2)

冒泡排序，选择排序，插入排序的空间复杂度是O(1)

快速排序：

python为什么叫爬虫。