18 冒泡排序

另一种有趣的排序方法来了

大纲

• 冒泡排序的直观解释

• 编写函数

• 减少冗余循环

• 增加升序或降序参数

冒泡排序的思想是比较相邻两个数字的大小，如果不满足则进行交换，例如先比较第1个和第2个，根据条件进行交换操作，再比较第2个和第3个，这要最大的数字就像是冒泡一样，逐步跑到最后的位置上。这样完成了一轮操作，然后再对前面n-1个数字再来一轮冒泡，这样多轮后，整个数据序列成为一个有序的序列。

冒泡的直观解释

如果将上述思想用代码表达出来，就是如下的样子。基本上是一个双重循环，每次我们把中间结果打印出来，可以帮助我们理解整个过程。

x = [3,4,1,12,9,8]

for i in range(len(x),0,-1):
    print("i=",i)
    for j in range(i-1):
        print("j=",j,end=' ')
        if x[j]>x[j+1]:
            x[j], x[j+1]=x[j+1],x[j]
            print(x)

i= 6
j= 0 j= 1 [3, 1, 4, 12, 9, 8]
j= 2 j= 3 [3, 1, 4, 9, 12, 8]
j= 4 [3, 1, 4, 9, 8, 12]
i= 5
j= 0 [1, 3, 4, 9, 8, 12]
j= 1 j= 2 j= 3 [1, 3, 4, 8, 9, 12]
i= 4
j= 0 j= 1 j= 2 i= 3
j= 0 j= 1 i= 2
j= 0 i= 1

x

[1, 3, 4, 8, 9, 12]

编写函数

把代码变成一个函数，就可以当作是内置函数那样使用了。

def sort_list(x):
    for i in range(len(x),0,-1):
        for j in range(i-1):
            if x[j]>x[j+1]:
                x[j], x[j+1]=x[j+1],x[j]
    return x

sort_list([14,6,7,4,9,30])

[4, 6, 7, 9, 14, 30]

减少冗余的循环

如果在上一轮的循环中，发现已经没有交换操作了，意味着数列已经排好了，这时就不需要继续循环了。所以这里加上一个判断条件。

def sort_list(x):
    for i in range(len(x),0,-1):
        swap = True # 判断是否有交换
        for j in range(i-1):
            if x[j]>x[j+1]:
                x[j], x[j+1]=x[j+1],x[j]
                swap = False
        if swap: 
            break
    return x

sort_list([14,6,7,4,9,30])

[4, 6, 7, 9, 14, 30]

增加升序或降序的参数

排序可以有升序，也可以有降序，让我们来把函数加入这些可选择的参数，丰富它的功能。

def sort_list(x, order=0):  # 0 为升序，1为降序
    for i in range(len(x),0,-1):
        swap = True # 判断是否有交换
        for j in range(i-1):
            if (x[j]>x[j+1] and order==0) or (x[j]<x[j+1] and order==1):
                x[j], x[j+1]=x[j+1],x[j]
                swap = False
        if swap: 
            break
    return x

sort_list([14,6,7,4,9,30],order=0)

[4, 6, 7, 9, 14, 30]

sort_list([14,6,7,4,9,30],order=1)

[30, 14, 9, 7, 6, 4]