Python数据结构与算法（12）---冒泡排序

冒泡排序

冒泡排序，其英文为Bubble Sort。是指把一组数据从左边开始依次进行两两交换，小的方前面，大的放后面，通过反复比较一直到没有数据需要交换为止。

该排序方法由于很像水里的泡泡，从水底冒出的，故称之为冒泡排序。

冒泡排序原理

冒牌排序的原理如下：

1.从列表开始，依次两两比较值的大小，把大的往后交换，一直到末尾，这样列表中最大的值肯定就是末尾的值。

2.接着，在从列表开始，两两比较知道交换到倒数第二位，那么第二大的值确定。

3.依次循环到只剩1，完成所有数的交换后，冒泡排序即完成。

比如，我们现在又一个列表值为[8,0,4,3,2,1]，那么我们需要进行5轮循环。

第1次循环的图解：

第2次循环的图解：

第3次循环的图解：

第4次循环的图解：

第5次循环的图解：

从上面的图我们可以发现，我们的列表是6位元素，但是我们只循环了5次，就得到了最终结果。所以冒牌排序顶层循环的次数，一定等于列表的长度减1。

后面我们比较数字的时候，一次漏掉一个元素，这是因为最大的数据依次放到了后面，所以，内层循环的次数是每经过外层循环1次少1次，直到为0结束。

也就是说，内层次数只要减去外层循环次数，自然是每次减1，毕竟外层是每次加1。

Python代码实现冒泡排序

既然原理都已经通过图解介绍清楚了。下面，就应该介绍如何使用Python代码实现冒泡排序算法。示例代码如下所示：

s_list = [8, 0, 4, 3, 2, 1]
print("排序之前的结果：", s_list)
for i in range(0, len(s_list)):
    for j in range(len(s_list) - i - 1):
        if s_list[j] >= s_list[j + 1]:
            temp = s_list[j + 1]
            s_list[j + 1] = s_list[j]
            s_list[j] = temp
print("排序之后的结果：", s_list)

运行之后，效果如下：