一、冒泡排序简介
冒泡排序(Bubble Sort)是一种常见的排序算法，相对来说比较简单。
冒泡排序重复地走访需要排序的元素列表，依次比较两个相邻的元素，如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换，则元素列表排序完成。
在冒泡排序中，值最大(或最小)的元素会通过交换慢慢“浮”到元素列表的“顶端”。就像“冒泡”一样，所以被称为冒泡排序。
二、冒泡排序原理
冒泡排序的原理如下：
. 比较相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列，降序则反过来)。
. 从列表的开始一直到结尾，依次对每一对相邻元素都进行比较。这样，值最大的元素就通过交换“冒泡”到了列表的结尾，完成第一轮“冒泡”。
. 重复上一步，继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以，已经“冒泡”到后面的元素即使比较也不需要交换，不比较可以减少步骤)。
. 继续从列表开始进行比较，每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减，一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较)，则列表排序完成。
以列表 [, , , , , , , , , , , ] 进行升序排列为例。列表的初始状态如下图。
要进行升序排列，则大的元素要依次“冒泡”到列表的结尾。
. 从列表的开头，比较相邻的两个元素，如果第一个值比第二个值大则交换。小于，不需要交换。
. 向列表的结尾方向“走访”，比较第二组相邻的元素(第二个和第三个)，如果不是从小到大则交换。小于，不需要交换。
. 继续“走访”，比较第三组相邻的元素，如果不是从小到大则交换。大于，所以需要交换。
. 对顺序错误的元素进行位置交换。交换和的位置。
. 一直“走访”到结尾，第一轮“冒泡”结束后，值最大的元素“冒泡”到了列表的结尾。“冒泡”到了列表结尾。
在下一轮“冒泡”中，不需要再将进行比较，需要比较的元素个数减。
. 从列表开头，重复下一轮“冒泡”，每进行一轮“冒泡”，需要比较的元素都少一个，直到没有元素对需要比较时，整个列表排序完成。排序结果如下图。
三、Python实现冒泡排序
四、冒泡排序的时间复杂度和稳定性
. 时间复杂度
在没有特殊说明时，一般都是计算最坏时间复杂度。
在冒泡排序中，最坏的情况是元素列表的初始状态是完全逆序排列的，需要进行 n- 轮“冒泡”，每一轮“冒泡”需要进行 n-i 次比较和交换操作。i 的平均值为 n/ ，时间复杂度为 T(n)=n(n-)/ ，再乘每次操作的步骤数(常数，不影响大O记法)，所以冒泡排序的时间复杂度为 O(n^) 。
. 稳定性
排序算法的稳定性指，当元素列表中有相等的元素时，相等元素的相对次序是否固定不变，如果相对次序固定不变，则排序算法是稳定的，反之。
在冒泡排序中，每次比较两个元素，当元素的大小顺序错误时才会进行交换，如果元素列表中有两个相等的元素，它们最终肯定会相邻在一起，但对它们比较时不会进行交换，相对次序是保持不变的。所以冒泡排序是一种稳定的排序算法
