冒泡排序 bubble sort

思想：“冻结”列表的长度，然后进行遍历，把最大数推到最后，然后将“冻结”的长度减1，重复此操作。
冒泡排序原理是从第一项开始，将第一项 a 和第二项 b 比较，如果 a < b，则不动，否则交换两者的顺序。然后将第二项 b 和第三项 c 比较，和前面是一样的。重复此过程直到最后一项。

def bubble_sort(lst):
    length = len(lst) #1
    while length > 0: #2
        for i in range(length-1): #3
            if lst[i] > lst[i+1]:
                lst[i], lst[i+1] = lst[i+1], lst[i] #4
                print(lst) #5
        length -= 1 #6
    return lst

#1 可以理解这是未经排序的部分的长度。
#2 当这个未经排序的部分长度为 0 时，结束循环，排序完成。
#3 从第一项开始进行两两比较。为什么只循环到 length-1，因为是 lst[i] 和后一项 lst[i+1] 比较，如果 lst[i+1] 是最后一项，也就是要满足 i+1 <= length-1，否则 IndexError。
#4 是一个 Pythonic 的写法。传统的换值写法是：

temp = lst[i]
lst[i] = lst[i+1]
lst[i+1] = temp

显然 Python 的写法更加简洁明了。
#5 用于观察列表的每次变化。
#6 冒泡法的特点是两两比较，大的数往后移动，那么一轮遍历下来，最大的数就到了最后，那么第二轮就不必再遍历它。
我们来看变化过程：

[5, 4, 3, 2, 1] # input
-----------------
[4, 5, 3, 2, 1] 
[4, 3, 5, 2, 1]
[4, 3, 2, 5, 1]
[4, 3, 2, 1, 5]
[3, 4, 2, 1, 5]
[3, 2, 4, 1, 5]
[3, 2, 1, 4, 5]
[2, 3, 1, 4, 5]
[2, 1, 3, 4, 5]
[1, 2, 3, 4, 5]

可以明显看到 5 被一点点推到右边去，像冒泡一样。
后面的数字以此类推。
总而言之就是，每一次遍历整个表，都会把最大的数推到最后，然后忽略最后一项，继续遍历剩下的元素。直到剩下 0 个元素为止。