52、排序和冒泡法

成长是每个人一辈子的事情，它无关乎年纪。无论何时，停滞成长，才是最可怕的衰老！

回忆一下上回学习的知识：
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)