# 18 冒泡排序

## 大纲

* 冒泡排序的直观解释
* 编写函数
* 减少冗余循环
* 增加升序或降序参数

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

## 冒泡的直观解释

![](https://4271017341-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MOnn9RVvu2dqZZMH3zA%2F-MOntNPIJ85Smcb3zaAX%2F-MOnu_iU_K8kAYpFAX9-%2FbubbleSort.gif?alt=media\&token=dadccb47-29a5-44d4-8850-21c6a1eae1d6)

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

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

```python
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
```

```python
x
```

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

## 编写函数

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

```python
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
```

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

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

## 减少冗余的循环

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

```python
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
```

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

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

## 增加升序或降序的参数

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

```python
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
```

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

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

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

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