首先，列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数…… 会发生什么？
- 时间复杂度:
O(n**2) - 空间复杂度:
O(1) - 排序稳定性: 稳定
代码关键点：
- 趟
- 无序区
分析：
- 假设有n个数，那么下标就是从0开始，一直到n-1,所以下标是【0，n-1】；
- 每一趟，都会将最大的一个数排上去，到最后两个数的时候，只用排一个，就完成了所有的排序。所以排序趟数总共是(n-1)；(也可以写n，不过只是形同虚设，没有实际意义罢了，这趟排不排都不影响结果，相当于可忽略）。
- 第i趟的时候，比如第3趟，相当于前面已经完成了0,1,2趟，有序区已经有3个数，即有序区有** i** 个数，无序区有(n-i)个数，下标是【0，n-i-1】。但是，箭头只用从下标【0，n-i-2】与上一个数【1，n-i-1】进行比较就可以完成大小判断。事实上，无序区从最下面往最上面进行比较，实际发生的排序次数比实际数值数量少1。比如，从上到下1，2，3。3和2比，3上去.然后再是1和3比，3上去，只用2次就ok了。
初始版本
import random
def bubble_sort(li):
for i in range(len(li)-1): # i表示第i趟 一共n或者n-1趟
for j in range(len(li)-i-1): # 第i趟 无序区[0, n-i-1] j表示箭头 0~n-i-2
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
return li
li = list(range(10000))
random.shuffle(li)
bubble_sort(li)
优化版
如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法。
import random
def bubble_sort(li):
for i in range(len(li)-1): # i表示第i趟 一共n或者n-1趟
exchange = False
for j in range(len(li)-i-1): # 第i趟 无序区[0, n-i-1] j表示箭头 0~n-i-2
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
break
return li
li = list(range(10000))
random.shuffle(li)
bubble_sort(li)
- 如果列表是无序的，在第一次排序的时候，一定会检查出来数值大小的差异，一定会进行数值交换；
- 如果列表是有序的，第一趟排序的时候，从上到下，一次都没有发现数据大小是异常的，也就没有进行一次交换；
