1、简介

冒泡排序，把一组无序的序列，变成有序的序列。思路：列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数….
算法关键点：1、有序区 2、无序区
原理：在无序区中，通过n-1趟中的(n-i-1)次比较，把最大值(从小到大排序)或者最小值(从大到小排序)依次放在序列的最后面，生成有序区

二、图解分析冒泡

现已列表[7,5,4,6,3,8,2,9,1] 为例，我们通过这个列表按从小到大的方式排序，来说明冒泡排序的过程。首先原生无序列表如下：
image.png
第一趟：此次循环的多次比较交换，使得最的大数字9冒到了最上面，这样 9 就在有序区中。
image.png
第二趟：此次循环的多次比较交换，使得最的大数字8冒到了最上面，这样 [8,9] 就在 有序 序列中。
image.png
你会发现，这次循环比前面少一次循环比较。
这是因为第一次循环时已经把最大的 9 排到最上面的位置了，这次排序肯定不会去占用最上面的位置的，所以此时比较次数可以比前面少一次。
第 八 趟：依次类推，一共只需要走 8 趟即可，使得最的大数字 2 也上去了，但是 因为 最后 一个 1 已经不需要再比较了。
image.png
所以这个倒数第二趟，也就是 第 八 趟上去之后，这个算法就算结束了，所以一共走了 8 趟
得出结论：
外层循环是: n-1，则内存循环比较的次数则为：n - i - 1

3、冒泡排序实现

3.1、冒泡排序

根据上面的思路我们接下来实现冒泡排序的代码，代码如下：

  1. import random
  3. def bubble_sort(li):
  4.     for i in range(len(li) - 1):
  5.         for j in range(len(li)-i-1):
  6.             if li[j] > li[j+1]:
  7.                 li[j],li[j+1] = li[j+1],li[j]
  9. #测试
  10. data = list(range(100))
  11. random.shuffle(data)  #shuffle：洗牌的意思，就是把有序的列表变成无序的
  12. bubble_sort(data)
  13. print(data)

3.2、冒泡排序优化

如果冒泡排序中执行一趟而没有交还，则列表已经是有序状态，可以直接结束算法。比如说：[1,2,3,4,5,6]我已经是有序的了，所以一趟过后就不需要再排序了。

  1. def bubble_sort(li):
  2.     for i in range(len(li) - 1):
  3.         exchange = False
  4.         for j in range(len(li)-i-1):
  5.             if li[j] > li[j+1]:
  6.                 li[j],li[j+1] = li[j+1],li[j]
  7.                 exchange = True  #如果发生交换，说明是无序的，则exchange = True
  8.         if not exchange:   #这边没有交换，则是有序的，就不用再执行下一趟了
  9.             break

这个一般用于极端情况。最好记住下面这一个，肯定要记住上面那一个。如果想要比较一下快慢，则可以采用装饰器测试一下，不会写，二分法博客中有。
时间复杂度：O(n²)