开发者学堂课程【Python入门 2020年版：冒泡排序优化】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/639/detail/10301
冒泡排序优化
内容介绍
一、练习题讲解
二、冒泡排序优化
一、练习题讲解
课后题一
#有一个列表 names，保存了一组姓名 names=[ " zhangsan ' , ' lisi ' , ' chris ' , ' jerry ' , 'henry ' ]
#再让用户输入一个姓名，如果这个姓名在列表里存在，提示用户姓名已存在;
#如果这个姓名在列表里不存在，就将这个姓名添加到列表里。
答案：
1.使用 in 运算符
names=[ 'zhangsan ' , ' lisi ' , ' chris ' , ' jerry ' , 'henry ' ]
//列出列表中的元素
username = input ( ‘ 请输入一个用户名: ’ )
//提示输入用户名，赋给变量 username
if username in names: //如果 username 在 names 里
print(‘用户名已经存在’)//显示已经存在
else: //如果不在
names.append(username)
//将输入的 username 加进列表中去
2. 使用遍历
l 错误写法
names=[ ' zhangsan ' , ' lisi ' , ' chris ' , ' jerry ' , 'henry ' ]
//列出列表中的元素
username = input ( ‘ 请输入一个用户名: ’ )
for name in names:
if username == name
print(‘用户名已经存在’)
break
else: //else 与 if 对齐会使得，执行了 if 就随之执行 else
names.append(username) //就会错误的添加多余数据
print(names)
此时不能将 else 与 if 相对应，因为当输入 lis i时，处于第一次循环，输出的元素是与第一个元素 zhangsan 进行比较的，在 if 判断时两者不相等，若写成当前的 else 格式则会把 lisi 加进列表中，但其实列表中下一次循环含有 lisi。
所以我们应该改成 for 与 else 相对。变为当 for 循环退出之后，再执行 else。
正确写法（else 与 for 对齐）
names=[ ' zhangsan ' , ' lisi ' , ' chris ' , ' jerry ' , 'henry ' ]
//列出列表中的元素
username = input ( ‘ 请输入一个用户名: ’ )
//提示输入用户名，赋给变量 username
for name in names: //遍历列表中的每个元素
if username == name //如果输入的值存在
print(‘用户名已经存在’) //提示已存在
break //退出循环
else: //循环结束之后，如果都不存在
names.append(username)
/则把当前输入的 username 元素加入列表中
print(names) //输出查看最后列表中含有的元素
else 与 for 对齐，会等待循环结束，输入的元素被一一与列表中元素判断后，再选择是否加入元素。如输入 lisi，会提示用户已经存在，而输入 jack 则会将其加入到列表中。
输出[ ' zhangsan ' , ' lisi ' , ' chris ' , ' jerry ' , 'henry ' ,'jack']
二、冒泡排序优化
首先定义一组列表数据，现要对数据进行排序，根据冒泡排序的核心思想，将当前数不断和下一个数进行比较。
我们写一个 while 循环，循环次数为 len(nums)-1,因为在比较中我们最多可以取到倒数第二个数进行比较，因为最后一个数没有下一个数可以比较。再使用 if nums [i] > nums [i+1] 判断前一个数和后一个数之间的大小，
如果前一个数大于后一个数，交换两者位置。到此就完成了一次循环。但我们需要比较多趟，所以再添加一个循环。循环次数为同为 en(nums) - 1。到此输出结果就变为有序。
代码
#冒泡完善
nums = [6,5,3,1,8,7,2,4]
j= 0
while i < len(nums) - 1:
j += 1
i = 0
while n <len(nums) - 1:
//如果前一个数据大于后一个数据
count += 1
if nums [i] > nums [i+1]
//交换位置
nums[i]，nums[i + 1] = nums[i + 1] , nums[i]
i += 1
print(nums) //输出排序后的列表
print(‘比较了%d次’ % count)//比较次数，复杂度为o(n-1)的平方
输出结果
[1，2，3，4，5，6，7，8]
比较了49次
至此共比较了49次，因为列表共有8个数，每趟比较7次，共比较7趟，所以为7*7=49次。复杂度为 o(n-1)的平方，如n=8，则49次。其中也有许多重复比较的过程。
1.优化每一趟比较次数
如在第一趟中，是每个元素都互相比较，比较8次。
但在第二趟比较时，5和3，1比较时交换，但在与6，7比不交换。
7与4比时交换，但最后7与8其实并没有比较的意义。因为冒泡排序每一趟都是找到一个最大数，第一趟就已经找到了最大数8在末尾。所以我们可以将其删减优化。
依次类推在第三趟时，最后6和7，8都无需比较。
总结：每次多比较的次数就是j的值。
#第一趟比较时，j=0,多比较了0次
#第二趟比较时，j=1,多比较了1次
#第三趟比较时，j=2,多比较了2次
代码
nums = [6,5,3,1,8,7,2,4]
count = 0
j= 0
#第一趟比较时，j=0,多比较了0次
#第二趟比较时，j=1,多比较了1次
#第三趟比较时，j=2,多比较了2次
while i < len(nums) - 1:
i = 0
while n <len(nums) - 1-j: //在每次比较时减去多余的次数j
count += 1
if nums [] > nums [i+1]
nums[i]，nums[i + 1] = nums[i + 1] , nums[i]
i += 1
//要将 j+=1写在末尾，否则初始值就变为了1，在减次数时就会多减
j += 1
print(nums)
print(‘比较了%d次’ %count)
输出结果
[1，2，3，4，5，6，7，8]
比较了28次
代码中j为比较的趟数，i为比较的次数，所以要减少每趟多余比较的次数，只需要将次数变为<len(nums) -1 -j，同时将j+=1放在最后即可;此时第一次比较就会变为7趟，第二次比较就会变为6趟，依次递减。优化之后复杂度变为2/n(n-1),总比较次数变为28次。
2.优化总比较趟数
但在第六趟的比较过程中，列表的值已变为有序的。但仍在重复进行比较。同理此后的第七次根本没有必要执行。
所以我们可以对总比较趟数进行优化，在每一趟之后定义一个 flag,设置其初始值为 True 假设每一趟都没有换行，同时在一趟比较之后，falg 依然为 True，说明本趟没有进行数据的交换，那么就执行 break 退出循环。
最后优化结果变为比较27次，因为当第六趟发现数据不在进行交换时，就退出了循环。最后的第七趟没有再比较。
代码
nums = [6,5,3,1,8,7,2,4]
count = 0
j= 0
#第一趟比较时，j=0,多比较了0次
#第二趟比较时，j=1,多比较了1次
#第三趟比较时，j=2,多比较了2次
while i < len(nums) - 1:
#在每一趟里都定义一个 flag
flag=True #假设每一趟都没有换行
i = 0
while n <len(nums) - 1-j:
count += 1
if nums [i] > nums [i+1]
#只要交换了，说明 flag 不对为 false
falg=False
nums[i]，nums[i + 1] = nums[i + 1] , nums[i]
i += 1
if flag:
#这一趟走完，flag 依然是 Ture，说明这一趟没有进行过数据交换
break//停止循环
j += 1 //进行下一趟
print(nums)
print(‘比较了%d次’ %count)
输出结果
[1，2，3，4，5，6，7，8]
比较了27次
总结
设立一个 flag=Ture，当发现本趟未执行数据交换时，就不会执行 if nums [i] > nums [i+1]， flag 不变为 false，执行 if flag:
后的 break 退出循环。
2. 一键替换变量名
Tip:一键替换代码中的 flag 变量名，直接双击 flag，右键找到 Refactor 的 Rename 重命名将其改为要更换的变量名 a 即可。
4.优化效果
在列表数据为[6,5,3,1,8,7,2,4]这样乱序时优化并不明显。但是当列表的数据几乎排序好时，如[1,2,3,4,5,6,7,9,8]，在未优化时仍需要64次，但加上优化每一趟比较次数之后仅需要36次,而优化总比较趟数之后就变为15次。
