排序算法三：冒泡排序

一、原理

冒泡排序的原理很简单， 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从Z到A）错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。

冒泡排序不管在什么情况下，时间复杂度都是O(\(n^2\))。

对比插入排序来说，在平均的情况下，插入排序性能是冒泡排序的两倍。

图例：

以数组[54, 15, 34, 82, 15, 46, 85, 43]为例：

第一次循环先比较54和15，54大于15，交换两个元素：

比较54和34，54大于34，交换两个元素：

比较54和82，54不大于82，不交换：

比较82和15，82大于15，交换两个元素：

按照相同的方式一直对比，直到最后，85被移动到最后：

此时完成一轮冒泡排序，接下来将剩下的元素再次执行同样的操作即可完成对整个数组的排序。

二、代码实现

2.1 C++实现

2.2 python实现

三、冒泡排序的优化

当对第x个数据排序时，冒泡排序每次都会遍历剩下的n-x个元素，即使整个序列已经有序。

因此可以在这一个层面进行优化，如果序列已经有序了，则后面的排序就无需进行了，可以添加一个标记字段来处理这个问题。