Python习题练习7-- 冒泡排序
题目：冒泡排序（就是让一组数从小到大进行排列，假设一组数为[9,1,5,4]，让其从小到大进行排序）
看到题目让对一组数字进行排序，我们首先想到最简单的办法是直接使用内置函数sorted()进行排序，这个思路是没有问题的，在大部分时间写代码的时候完全可以直接用sorted()函数进行排序，但是有时候面试让对数字进行排序时，可不能光说使用sorted()进行排序，我们也需要知道其他的排序方法，这次先说下比较经常听到的冒泡排序。
一、使用while循环
a = [9,1,5,4] #把需要排序的数字定义一个变量ab = len(a) #计算a的长度，然后给到变量bc=1 #定义c的值为1while c < b: #写一个while循环，确定需要排序的次数for j in range(0,b-c): #定义一个range()，是为了得到每次是那几个数进行比较if a[j]>a[j+1]: #让相邻的两个数进行比较a[j],a[j+1] = a[j+1],a[j] #如果满足第一个数大于第二个数，则交换位置c=c+1 #每进行过一次需要给c加上1，去进行while循环的判断print(a) #打印a的结果为：[1, 4, 5, 9]
解题思路：首先要先了解冒泡排序的概念，说白了就是让相邻的两个数进行比较，如果第一个数比第二个数大就交换位置，然后再用第二个数和第三个数进行比较，如果第二个数比第三个数大就再交换位置，根据题目来说就是，9、1、5、4，先让9和1进行比较，发现9比1大，然后让9和1交换顺序，此时列表就是1、9、5、4，然后再让第二个数和第三个数比较，就是9和5去比较，9比5大，再交换顺序，此时列表就变成了了1、5、9、4，最后再让9和4进行比较，发现9还是比4大，然后再去让9和4进行换位，此时列表就是1、5、4、9，这样一轮下来后就能把最大的一个数放最右边了，然后再去进行第二轮比较，第二轮和第一轮一样，第二轮结束后，列表应该变为1、4、5、9，然后再进行一轮比较就能完成整个冒泡排序了。
第一步首先根据上面理解开始梳理流程：
if a[j]>a[j+1]: #让相邻的两个数进行比较a[j],a[j+1] = a[j+1],a[j] #如果满足第一个数大于第二个数，则交换位置
我是想着先把两个相邻的两个数互相换位置的这个先写出来，然后再去想其他的东西，就是让两个相邻的数去进行比较，如果第一个数大于第二个数，就互换位置，a[j]就是根据下标取列表中的值。a[j]和a[j+1]根据取下标肯定就是两个相邻的值了，然后进行比较如果满足条件，直接用a[j],a[j+1] = a[j+1],a[j]就可以让他俩互换位置了。
第二步就是要考虑j的值了：
a = [9,1,5,4] #把需要排序的数字定义一个变量ab = len(a) #计算a的长度，然后给到变量bfor j in range(0,b-1): #定义一个range()，是为了得到每次是那几个数进行比较if a[j]>a[j+1]: #让相邻的两个数进行比较a[j],a[j+1] = a[j+1],a[j] #如果满足第一个数大于第二个数，则交换位置
因为这个列表有四个数，所以j取下标的话就是用a[0]到a[3]就能代表了列表里的所有数了，但是如果j=3的话，a[j+1]就是a[4]，但是没有a[4]这个值，所以j的范围就只能是0到2，这样j的范围就确定了。然后我们可以用len()求出列表的数有4个，因为要把范围放到ragne函数中，让去进行遍历递增，所以我们range()里填的数就是range(0,3)（range()的定义就是包含前面的数，不包含后面的数，所以range(0,3)代表的就是0，1，2），又因为b=4所以就可以写成是range(0,b-1)。先理解b-1的含义，具体开头为什么是b-c，到第四步会有解释。
第三步要确定进行几次排序：
a = [9,1,5,4] #把需要排序的数字定义一个变量ab = len(a) #计算a的长度，然后给到变量bc=1 #定义c的值为1while c < b: #写一个while循环，确定需要排序的次数for j in range(0,b-1): #定义一个range()，是为了得到每次是那几个数进行比较if a[j]>a[j+1]: #让相邻的两个数进行比较a[j],a[j+1] = a[j+1],a[j] #如果满足第一个数大于第二个数，则交换位置c=c+1 #每进行过一次需要给c加上1，去进行while循环的判断print(a) #打印a的结果为：[1, 4, 5, 9]
第二步每执行一次就会排出一个最大的值，为了完成整个列表的排序，我们需要排b-1次（b是列表中数据的个数，按照实际例子说，题中有4个数，第一次排序确定了9，第二次排序确定了5，第三次排序确定了4，这时候只剩一个了，就不需要再去对1进行一次排序了，所以排序次数就是b-1次），所以就可以写个while循环，设定c的值为1，每执行一次第二步，让c+1，直到c满足c<b时，结束循环（最好的理解是写成c<=b-1，但是c<=b-1不就是c<b吗）
第四步优化：
a = [9,1,5,4] #把需要排序的数字定义一个变量ab = len(a) #计算a的长度，然后给到变量bc=1 #定义c的值为1while c < b: #写一个while循环，确定需要排序的次数for j in range(0,b-c): #定义一个range()，是为了得到每次是那几个数进行比较if a[j]>a[j+1]: #让相邻的两个数进行比较a[j],a[j+1] = a[j+1],a[j] #如果满足第一个数大于第二个数，则交换位置c=c+1 #每进行过一次需要给c加上1，去进行while循环的判断print(a) #打印a的结果为：[1, 4, 5, 9]
解释下为啥for j in range(0,b-c)里，不写b-1写成b-c,再进行排序时，我们第一轮得到最大值放到最右面后，到第二轮排序时只需要遍历a[0]到a[2]就行，然后第三轮时遍历a[0]和a[1]两个值就行，因为前两轮已经确定了左侧的值了，没必要再去进行遍历重复进行比较，所以这里直接用b-c就行，每进行一轮c的值就+1，然后b-c正好就是j的范围。
二、使用for循环
a = [9,1,5,4] #把需要排序的数字定义一个变量ab = len(a) #计算a的长度，然后给到变量bfor i in range(0,b): #定义要循环的次数for j in range(0,b-i-1): #定义一个range()，是为了得到每次是那几个数进行比较if a[j]>a[j+1]: #让相邻的两个数进行比较a[j],a[j+1] = a[j+1],a[j] #如果满足第一个数大于第二个数，则交换位置print(a) #打印a的结果为：[1, 4, 5, 9]
这两种有两个不同点
1、写循环的次数时，使用了for循环，知道要循环b-1次能得到答案，所以用for i in range(0,b)也可以解决这个问题
2、排序的range()范围，b-1是每次都要对所有的进行排序，但是为了让后面几轮已经排好位置的不用再进行一次比较，又因为i是从0开始每次循环后i都会加1，这里再减去i就行，理解形式和while循环的第四步类似。