成长是每个人一辈子的事情，它无关乎年纪。无论何时，停滞成长，才是最可怕的衰老！
回忆一下上回学习的知识：
1.几种变量（可变、不可变）类型：
元组是一个不可变列表，元素修改本质上用的内存地址，只要内存地址不变就没有问题，但内存地址是引用类型，房间里放的是什么那就是什么（不可以改变）；追求本质的时候再加深理解；
2.不是所有的函数都有返回值，不返回默认None
print语句——唯一任务，打印，不返回东西=返回None，默认返回None
a=print('b') #print函数打印值， 返回(out) None
3. API（方法、操作）
4. 特别注意namedtuple
名字和标识符是两码事，不可混淆_Point(名字)与Point（变量）；（为了明白这样理解）
排序算法是最常见的算法面试题目之一；（8种排序算法选一种）
排序算法看出一个人是否会写程序；
如果排序算法搞不定，呢么这个人基本就不会写程序；
8种排序算法必须现场写出来；
1.练习题目： 依次接收用户输入的3个数，排序(降序）后打印；
练习基本功：4个基本方法；锻炼逻辑思维能力；
# 方法1：使用分支结构完成
first_number = int(input('>>>'))
second_number = int(input('>>>'))
third_number = int(input('>>>'))
if first_number > second_number:
if first_number > third_number:
if second_number > third_number:
pass
else:
second_number,third_number = third_number,second_number
else:
first_number,third_number = third_number,first_number
third_number,second_number = second_number,third_number
else:
if first_number < third_number:
if second_number < third_number:
first_number,third_number = third_number,first_number
else:
first_number,second_number = second_number,first_number
second_number,third_number = third_number,second_number
else:
first_number,second_number = second_number,first_number
print(first_number,second_number,third_number)
-----------------------------------------
>>>789
>>>453
>>>908
908 789 453
# 方法2：使用max函数;
first_number = int(input('>>>'))
second_number = int(input('>>>'))
third_number = int(input('>>>'))
a = max(first_number,second_number,third_number)
if a == max(first_number,second_number):
if max(first_number,third_number) == a:
b = max(second_number,third_number)
else:
b = max(second_number,first_number)
if first_number < second_number:
c = first_number
else:
c = second_number
else:
b = max(second_number,first_number)
if first_number < second_number:
c = first_number
else:
c = second_number
print(a,b,c)
-------------------------------
>>>34
>>>23
>>>67
67 34 23
# 方法3;使用list.sorted
count = 0
flag = True
lst = []
while flag:
lst.append(int(input('>>>')))
count += 1
if count == 3:
flag = False
lst.sort(reverse=True)
lst
# 方法3变体
lst = []
for i in range(3):
lst.append(int(input('{} = '.format(i))))
lst.sort(reverse=True)
lst
-------------------------------------------------------
>>>45
>>>67
>>>34
[67, 45, 34]
# 方法4：冒泡法排序；
a = int(input('>>>'))
b = int(input('>>>'))
c = int(input('>>>'))
if a > b:
pass
else:
a,b = b,a
if b > c:
pass
else:
b,c = c,b
if a > b:
pass
else:
a,b = b,a
print(a,b,c)
----------------------------
>>>34
>>>78
>>>23
78 34 23
#效率低下的方法；
nums = []
out = None
for i in range(3):
nums.append(int(input('{} = '.format(i))))
while nums:
if len(nums) == 1:
print(nums[0])
break
m = max(nums)
print(m)
nums.remove(m)
------------------------------------------------------------------------------------
0 = 43
1 = 66
2 = 89
89
66
43
2.排序算法
常见的四种排序算法法：（*****）
1.冒泡法排序 Bubble sort
冒泡法
# map函数的利用
nums = list(map(int,'1 9 8 5 6 7 4 3 2 0'.split()))
print('raw_nums:',nums)
for j in range(len(nums)-1,0,-1): #第几趟；
for i in range(j): #完成22次比较；
if nums[i] < nums[i+1]:
nums[i],nums[i+1] = nums[i+1],nums[i]
nums
----------------------------------------------------------------------------------
raw_nums: [1, 9, 8, 5, 6, 7, 4, 3, 2, 0]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
冒泡法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)
网友评论