【引言】我们都经历过新生开学，一个班里几十个同学，军训的时候我们需要按照身高站成一队，个子高的站在后面，个子矮的站在前面。如果你是班主任的话，你会怎么让同学调整他们之间的位置，最终让所有的人都按照身高大小站好呢？

冒泡排序是一种通过两两对比的方式，依次找出最值的排序方式。

算法过程

使用冒泡排序来进行班级里面队伍的排列，就像是鱼在水里吐泡泡一样（应该会吐吧tx）。由于压强跟水深有关，所以泡泡从水底升到水面的过程中会逐渐的变大，最终变到最大升出水面。排列队伍也是一样，最高的那个人会在从前到后的两两对比中，最终站到队伍的最后面。

泡泡升出水面.png
班主任在排队的时候可以这么做（假设有 5 个同学）：
1、让全班同学 不分大小 站成一列，身高分别为（队伍从前到后）：150 165 160 173 155。
2、从前向后两两比较，首先比较1、2同学：150 165 160 173 155。
3、150 同学比 165 同学要矮，队伍保持不动，转而比较2、3同学：150 165 160 173 155。
4、165 同学比 160 同学要高，这样，两位同学 互换位置，以保证后面的要比前面的高：150 160 165 173 155。
5、继续比较3、4同学：150 160 165 173 155。
6、3 同学比 4 同学矮，所以队伍不进行变化：150 160 165 173 155。
7、继续比较4、5同学：150 160 165 173 155。
8、前面的 4 同学比后面的 5 同学高，所以交换位置：150 160 165 155 173。

这样就完成了第一次的队伍规整，我们可以看到，进行了第一次所有人的从前往后的两两对比，现在整只队伍最高的那个人已经站到了队尾，就像鱼吐泡泡一样，最大的泡泡已经浮出了水面。

继续从头到尾重复上面的过程，直到所有的人从前往后站队成从小到大。总体的过程就像是（队伍从下往上，过程从前往后）：
第一次整理：
155 155 155 155 155 173
173 173 173 173 173 155
160 160 165 165 160 160
165 165 160 160 165 165
150 150 150 150 150 150
第二次整理：
173 173 173 173 173 173
155 155 155 155 165 165
160 160 165 165 155 155
165 165 160 160 160 160
150 150 150 150 150 150
第三次整理：
173 173 173 173 173
165 165 165 165 165
155 155 160 160 160
160 160 155 155 155
150 150 150 150 150

就像这样，像鱼吐泡泡一样，逐渐的整个队伍就站成了从前往后，从大到到小的顺序。站队的过程，就是前面的同学和后面的同学比较，互换位置的过程。班主任就会很省事……

时间复杂度

当然，冒泡排序可以进行改进，增加一个标志位，如果一次遍历中没有发生值的交换，就证明整个数列都是有序的，这样，最好的情况下就是一开始整个序列就是有序的，所以，最好的情况下，时间复杂度是O(n)。

最坏的情况下，需要反复遍历所有的元素，这样，时间复杂度就会变成O(n^2)。

所以平均时间复杂度为O(n^2)。

算法实现

#coding:utf-8
import numpy as np

def bubble_sort(data):
    data_length = len(data)
    for i in range(data_length, 0, -1):
        for j in range(1, i, 1):
            if  data[j] < data[j-1]:
                data[j], data[j-1] = data[j-1], data[j]

array = np.arange(20)
np.random.shuffle(array)
array = list(array)
print('输入的数据: {}'.format(array))
bubble_sort(array)
print('排序之后的数据：{}'.format(array))

结果是：

冒泡排序的结果.png


上一篇：写给媳妇儿的算法（三）——选择排序
上一篇：写给媳妇儿的算法（五）——插入排序