关键点

• 无序区，一开始都是无序区
• 有序区，每次执行完有序区数量不断增大，无序区数量不断减小
• 排序的趟数
• 每趟比较的次数

10个数第一趟排序

以上图的10个数为例：

• 第一趟开始前：
  无序区：[1,3,5,6,4,7,2,9,8,10]
  有序区：[]
  第一趟比较：箭头从无序区第一个元素移动到第9个元素，共比较9次，最后一次比较完后箭头停止移动，如果再移动说明还会跟下一个元素比较，此时已经没有下一个元素
• 第一趟结束：
  无序区：[1,3,5,6,4,7,2,9,8]
  有序区：[10]

总结：

• n个数共需要排n-1趟(只剩最后一个元素无需再排)，每趟结束后有序区元素数量增加1，无序区元素数量减少1
• 每趟排序都是当前无序区的元素从头开始挨个比较，比较的次数即无序区的数量减1

趟数和每趟都从1开始：
第1趟开始：有序区数量0，无序区数量n，、需要比较的次数n-1，第1次,第2次,第3次...,第n-1次
第2趟开始：有序区数量1，无序区数量n-1，需要比较的比较次数n-2， 第1次,第2次,第3次...,第n-2次
第3趟开始：有序区数量2，无序区数量n-2，需要比较的比较次数n-3， 第1次,第2次,第3次...,第n-3次
第4趟开始：有序区数量3，无序区数量n-3，需要比较的比较次数n-4， 第1次,第2次,第3次...,第n-4次
第 i 趟开始：有序区数量 i-1，无序区数量 n-(i-1)=n-i+1，需要比较的比较次数n-i， 第1次,第2次,第3次...,第n-i次

下标一般都是从0开始，趟数和每趟都转换成从0开始：
第0趟开始：有序区数量0，无序区数量n，需要比较的次数n-1，第0次,第1次,第2次...,第n-2次
第1趟开始：有序区数量1，无序区数量n-1，需要比较的比较次数n-2， 第0次,第1次,第2次...,第n-3次
第2趟开始：有序区数量2，无序区数量n-2，需要比较的比较次数n-3， 第0次,第1次,第2次...,第n-4次
第3趟开始：有序区数量3，无序区数量n-3，需要比较的比较次数n-4， 第0次,第1次,第2次...,第n-5次
第 i 趟开始：有序区数量 i，无序区数量 n-i，需要比较的比较次数n-i-1， 第0次,第1次,第2次...,第n-i-2次

代码实现

def bubble_sort(li):
    n = len(li)
    for i in range(n-1):#n个数，共n-1趟
        for j in range(n-i-1):# j就是示例图中的箭头，对应上面的从第0趟开始计算，range(n-i-1)即 0~n-i-2
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]

对于一个无序列表排序，时间复杂度是O(n^2)
如果列表一开始就有序，如果一趟中比较后没有交换元素说明已经是有序列表了，这样复杂度可以优化到O(n)：

#优化后
def bubble_sort(li):
    n = len(li)
    for i in range(n-1):#共n-1趟
        exchange = False
        for j in range(n-i-1):#第i趟(i从0开始)，比较n-i-1次
            if li[j] > li[j+1]:#条件如果改成>=，相同的数也会互换，就变成了不稳定排序，稳定排序是值相同的数，原来在前面的排完后还是在前面
                li[j],li[j+1] = li[j+1],li[j]
                exchange = True
        if not exchange:
            break

复杂度总结

• 最好情况(列表本来就有序)，只要比较一趟，时间复杂度O(n)
• 平均情况(无序列表，某一趟后发现元素已经有序了)，时间复杂度O(n^2)
• 最坏情况(无序列表，一直到最后一趟结束才全部有序)，时间复杂度O(n^2)