成长是每个人一辈子的事情，它无关乎年纪。无论何时，停滞成长，才是最可怕的衰老！
回忆一下上回学习的知识：
1.几种变量（可变、不可变）类型：
元组是一个不可变列表，元素修改本质上用的内存地址，只要内存地址不变就没有问题，但内存地址是引用类型，房间里放的是什么那就是什么（不可以改变）；追求本质的时候再加深理解；
2.不是所有的函数都有返回值，不返回默认None
print语句——唯一任务，打印，不返回东西=返回None，默认返回None
a=print('b') #print函数打印值， 返回(out) None
3. API（方法、操作）
4. 特别注意namedtuple
名字和标识符是两码事，不可混淆_Point(名字)与Point（变量）；（为了明白这样理解）
排序
常见的四种方法：（*****）
面试中出现最多，问的最多的是 排序问题；
业务中更多写的是嵌套形式，逻辑应该是没有缝隙的；
1 可以自己写排序方法；
写成列表会更漂亮一点；
2. 使用Max/min函数；
nums=[]
for i in range(3):
nums.append(int(input('{}:'.format(i))))
while True:
cur=min(nums)
print(cur)
nums.remove(cur)
if len(nums)==1:
print(nums[0])
break
总结
1.效率高不高看方法；
2.for 循环相当于计数器；
3.移除最小值，虽然效率不高，但也是一种思路
3. 使用list.sort() ; # sort有自己的排序算法；
# 使用sort
nums=[]
out=None
for i in range(3):
nums.append(int(input('{}:'.format(i))))
nums.sort()
print(nums)
------------------------------
0:6
1:9
2:5
[5, 6, 9]
4.冒泡法
经典的4-5个排序算法，（考查的概率非常高*****）
凡是排序，结果一定是升序或降序；
1.冒泡法（三种基本算法之一，也是最简单的一种）；虽然效率不高，但是呢它是其他算法的基础；
冒泡法1
lst=[1,9,8,5,6,7,4,3,2]
n=len(lst)
count_swap=0 #
count=0
for j in range(n):
for i in range(n-1-j):
count+=1 #比较了36次
if lst[i]>lst[i+1]:
lst[i+1],lst[i]=lst[i],lst[i+1]
count_swap+=1 # 交换了25次；
print(lst,count_swap,count)
冒泡法2 ——优化实现避免不必要的比较（顺向）加个标记flag；
#只要是排序，完全反向的数据，优化没有效果，只能优化到这一步了；
---------------------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8, 9] 25 36
lst=[1,9,8,5,6,7,4,3,2]
n=len(lst)
count_swap=0 #
count=0
for j in range(n):
for i in range(n-1-j):
count+=1 #比较了36次
if lst[i]>lst[i+1]:
lst[i+1],lst[i]=lst[i],lst[i+1]
flag=True
count_swap+=1 # 交换了25次；
if not flag:
break
print(lst,count_swap,count)
---------------------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8, 9] 25 36
冒泡法2.2——使用封装与结构来交互数据；
#要求使用封装和解构来交互数据；
lst=[1,9,8,5,6,7,4,3,2]
n=len(lst)
for j in range(n):
for i in range(n-1-j):
if lst[i]>lst[i+1]:
#lst[i+1],lst[i]=lst[i],lst[i+1]
lst[i+1],lst[i]=lst[i:i+2] # 使用封装和解构 交互数据；
print(lst)
--------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8, 9]
冒泡法总结：
1.冒泡冒泡法需要数据一轮轮比较；
2.设定一个标记判断比较是否有数据交换发生，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序；
3.最差的排序情况是，初始顺序与目标顺序完全相反，遍历次数1,...,n-1之和n(n-1)/2
4.最好的排序情况是，初始顺序与目标顺序完全相同，遍历次数n-1
5. 时间复杂度O(n2)
6.封装与结构用于交互数据；
小结：
1. 时间复杂度计算：只看最高次方，其他都忽略不计；
三层循环 时间复杂度：O(n3) 效率低下；
n(n-i-1)=n**2-ni-n
2. 空间复杂度O(1) #只用了一个变量交换，其他的都是就地交换，两两交换；
3. 算法优化： O(n*2)-O(n)-O(1)
网友评论