算法（未完待续）

• 一.算法基础
• • 时间复杂度
  • • 对于简单问题的复杂度判断
  • 空间复杂度
  • 递归
  • • 实例：汉诺塔问题
  • 列表查找（线性表查找）
  • • 顺序查找
    • 二分查找
  • 排序
  • • 冒泡排序
    • 选择排序
    • 插入排序
    • 快速排序
    • 堆排序

用来评估算法效率的一个式子。
O(1)：可以理解为大约1个运行单位
O(n)：可以理解为大约运行n个运行单位

print('hello') #O(1)
for i in range(n):#O(n^2)
    print('Hello')
    for j in range(n):
        print('Hello')
while n>1:#如果n=64，运行6次，O(logn)。循环减半O(logn)
    print(n)
    n=n//2      

常见时间复杂度排序
O(1)2)2logn)3)
复杂问题的时间复杂度
O(n!)O(2ⁿ)O(nⁿ)

• 确定问题规模n
• 循环减半过程logn
• k层关于n的循环n^k

评估算法内存占用大小
算法用到了几个变量：O(1)
算法用了长度为n的一维列表：O(n)
算法使用了m行n列：O(mn)

两个特点：调用自身&结束条件

移动圆盘
n个圆盘：
1.把n-1个圆盘从A柱经过C移动B
2.将第n个圆盘从A移动到C
3.将n-1个盘子从B要经过A移动到C

#hannuota
def hano(n,a,b,c):
    if n>0:
        hano(n-1,a,c,b)
        print('移动圆盘，从{}到{}'.format(a,c))
        hano(n-1,b,a,c)

查找

• 输入：列表，带查找的元素
• 输出：元素下标
• python内置函数：index()

线性查找，从头找到尾 O(n)

def linear_search(li,val):
    for ind,v in enumerate(li):
        if v==val:
            return ind
    else:
        return None
print(linear_search([1,2,3,4,5,6],1))

#enumerate用法
ls=[1,,2,3,4,5]
dict={1:'a',2:'b',3:'c'}
for ind,val in enumerate(ls):
    print(ind,val)
for ind,val in enumerate(dict):
    print(ind,val)#默认返回key值及索引

折半查找，从有序列表的初始候选区开始，对查找的值与候选区中间值比较，减少候选区O(logn)
左右元素确定候选区，候选区中确定中间元素

def bin_search(ls,val):
    left=0
    right=len(ls)-1
    while left <=right:
        mid = (left + right) // 2
        if mid == val:
            return mid
        elif ls[mid] > val:
            rigtht = mid - 1
        else:
            left = mid + 1
    else:
        return None
print(bin_search([1,2,3,4,5,6,7,8,9,10,11,12],5))

比较相邻的数，将大的数往后冒。无序区，有序区（冒泡结果）
第n趟，无序区O(n²)

def bubble_sort(ls):
    #第i趟
    for i in range(len(ls)-1):
        for j in range(len(ls)-i-1):#无序区
            if ls[j]>ls[j+1]:
                ls[j+1],ls[j]=ls[j],ls[j+1]
                
ls=[random.randint(0,1000) for i in range(1000)]
bubble_sort(ls)
print(ls)
#优化，在某一趟没有任何交换，则可认为排序完成
def bubble_sort(ls):
    #第i趟
    for i in range(len(ls)-1):
        flag=False
        for j in range(len(ls)-i-1):#无序区
            if ls[j]>ls[j+1]:
                ls[j+1],ls[j]=ls[j],ls[j+1]
                flag=True
        if not flag:
           return

遍历找最小的

#很差，产生了新的列表，多占一份内存   O(n2)
def select_sort(ls):
    ls_new=[]
    for i in range(len(ls)):
        min_v=min(ls)
        ls_new.append(min_v)
        ls.remove(min_v)
    return ls_new

ls=[3,2,1,1,2,5,1]
print(select_sort(ls))

#找到最小的放到有序区，遍历无序区找到最小数放到有序区最后O(n2)
def select_sort(ls):
    for i in range(len(ls)-1):
        min_loc=i#无序区
        for j in range(i+1,len(ls)):
            if ls[j] 
插入排序 
有序区一张牌，从无序区拿数插入到有序区已经是有序区了
 
def insert_sort(ls):
    for i in range(1,len(ls)):#摸到的牌的下标
        tmp=ls[i]
        j=i-1#手里牌的下标最大的
        while ls[j]>tmp and j>=0:
            ls[j+1]=ls[j]
            j-=1
        ls[j+1]=tmp
    return ls

ls=[3,2,1,1,2,5,1]
print(insert_sort(ls))
 
快速排序 
取一个元素，使归位
列表分为两部分，左边比该元素小，右边比该元素大
递归排序
找一个数后，从右边找比该元素小的数放到左边放到该元素的位置，在左边找到比该元素大的数据放到（从右边找比该元素小的数）的位置
 
 
堆排序