一、原理
冒泡排序的原理很简单， 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序 （如从大到小、首字母从从 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++实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
template<typename T> void bubble_sort(vector<T> &data) { int i, j; for (i = 0; i < data.size() - 1; i++) { // 从最后一个元素，对比到当前的 data[i] 元素 // 因为对比的是 j 和 j - 1，所以循环条件是 j - 1 >= i，即 j > i for (j = data.size() - 1; j > i; j--) { if (data[j] < data[j - 1]) { swap(data[j - 1], data[j]); } } } } |
2.2 python 实现
|
1 2 3 4 5 6 |
def bubble_sort(data): size = len(data) for i in range(0, size - 1): for j in range(size - 1, i, -1): if data[j] < data[j - 1]: data[j - 1], data[j] = data[j], data[j - 1] |
三、冒泡排序的优化
当对第 x 个数据排序时，冒泡排序每次都会遍历剩下的 n-x 个元素，即使整个序列已经有序。
因此可以在这一个层面进行优化，如果序列已经有序了，则后面的排序就无需进行了，可以添加一个标记字段来处理这个问题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
template<typename T> void bubble_sort(vector<T> &data) { int i, j; bool again = true; for (i = 0; i < data.size() - 1 && again; i++) { again = false; // 从最后一个元素，对比到当前的 data[i] 元素 // 因为对比的是 j 和 j - 1，所以循环条件是 j - 1 >= i，即 j > i for (j = data.size() - 1; j > i; j--) { if (data[j] < data[j - 1]) { swap(data[j - 1], data[j]); again = true; } } } } |