一、原理

原理很简单， 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从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++实现

template<typename T>
void bubble_sort(vector<T> &data) {
    int i, j;

    // i的作用是控制遍历次数，n个元素的数组一共要执行n-1轮冒泡
    for (i = 0; i < data.size() - 1; i++) {
        // j从第二个元素开始，每次和前面的元素对比
        for (j = 1; j < data.size() - i; j++) {
            if (data[j] < data[j - 1]) {
                // 如果当前元素小于前一个元素，交换两个元素
                swap(data[j - 1], data[j]);
            }
        }
    }
}

2.2 python实现

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个元素，即使整个序列已经有序。

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

template<typename T>
void bubble_sort(vector<T> &data) {
    int i, j;
    bool again = true;
    
    for (i = 0; again && i < data.size() - 1; i++) {
        // 每开始新一轮冒泡，把标记置为false。
        again = false;
        for (j = 1; j < data.size() - i; j++) {
            if (data[j] < data[j - 1]) {
                swap(data[j - 1], data[j]);
                // 只有出现了逆序，才把标记置为true
                again = true;
            }
        }
    }
}