1.数据结构与算法
1：递归函数的特点：
- 1：调用自身
2：结束条件
def fun(x):
if x>0:
print(x)
fun(x-1)
fun(3)
#输出结果为：3，2，1
def fun(x):
if x>0:
print(x)
fun(x-1)
fun(3)
#输出结果为：1，2，3
汉诺塔案例
递归实例：汉诺塔问题
有"A",“B”,"C"三根柱子，"A"柱子上有n个盘子，求n个盘子移动到“C”柱子的次数和过程。
解决额外难题思路：
- [ n个盘子时]
-
1:把n-1个盘子从A经过C移动到B
-
2：把第n个盘子从A移动到C
-
3: 把n-1个盘子从B经过A移动到C
- 代码实现
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(3,"A","B","C")
-------------------------------------------------------------------------------------------------------------------------------
0：查找元素：
1：顺序查找
2：二分查找
1.1：顺序查找
顺序查搜索到元素找：也叫顺序查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止。
1.2代码实现：
def linear_search(li,val):
for ind,v in enumerate(li): #查看index,和对应index的取值
if v == val:
return ind
else:
return None
li = [2,3,5,6,8]
print(linear_search(li,5))
2.1：二分查找*
选定一个左指针和一个右指针分别是最左和最右的下角标；然后使用while循环判断右指针是否大于左指针，接着中间指针等于左右指针相加整除3（mid=left+right//2），再比较被查询的值和列表中mid指针对应的值，如果大于那就将mid指针赋值给left,假若小于那就mid赋值给right.一直判断直到left>right跳出循环。
def binary_search(li,val):
left = 0
right = len(li)-1
while right>left: #候选区里有值
mid = (right+left)//2
if li(mid)==val: #如果等于被查找的值就退出。
return mid
elif li(mid)>val: #如果中间的值大于被查找的值，被查找的值在mid的左侧
right = mid-1 #就需要将右指针往中间移。
else: #li(mid)<val 被查找的值在mid的右侧
left = mid+1
else:
return None
二分查找需要的是数据拍好顺序的，时间复杂度为lg(n)
------------------------------------------------------------------------------------------------------------------------
列表排序
概念：将一组“无序”的列表记录顺序调整为“有序”的记录顺序。
low_B三人组：
1：冒泡排序
2：选择排序
3：插入排序
1：冒泡排序
复杂度 = O(N^2)
原理：冒泡一共需要排序n-1趟（每一次排序后都添加一个数到有序列表的区间，当排序到
n-1趟时，最后一个已经是最大或者最小的就无需排序），每一趟中，比较相邻两个数前一个数比后一个大，那就进行交换，直到n-1趟都结束。
def bublle_sort(li):
for i in range(len(li)-1): #循环n-1趟
for j in range(i,len(li)-1): #每一趟中循环多少次
if li[j]>=li[j+1]:
li[j],li[j+1]=li[j+1],li[j]
return li
li = [4,3,6,5,20,8]
print(bublle_sort(li))
2：选择排序
复杂度 = O(N^2)
原理：循环n-1趟，然后取出每一趟的第一个指针，设为最小的值比较每一趟中无序列表取值，如果比设定的最小值小，那就进行交换，如果比最小值大那就是跟最小指针交换位置。
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1,len(li)): #每一趟都除去有序数据
if li[min_loc]>li[j]: #假若假设最小值比取出的值大，那就指针交换
min_loc = j
li[min_loc],li[i] =li[i],li[min_loc]
li = [2,5,4,7,6,9]
select_sort(li)
print(li)
3：插入排序
复杂度：O(N^2)
类似摸牌：摸第一张牌时，第一张牌是有序的，第二张牌需要跟第一张有序牌进行比较，是小还是大，确定位置在插入。一共循环n-1趟。
代码实现：
def insert_sort(li):
for i in range(1,len(li)): #摸到的牌的下角标
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
li = [2,5,4,7,6,9]
insert_sort(li)
print(li)
