算法思想
一个拥有若干元素的序列，重复遍历该序列，每一次遍历比较两个元素，将不符合指定排序规则的两元素交换，直到序列末端，则排序完成。该算法因为其排序的序列元素较大（或较小）者会在每次交换中慢慢浮到序列端部而得名冒泡排序。
实现步骤
以从小到大的顺序为例：
1.比较相邻的两个元素，如果第一个比第二个大则交换顺序
2.从第一对元素比较到最后一对元素，这样最大者排在序列最右端
3.重复步骤1，一直比较到倒数第二个元素
4.依此类推，持续对越来越少的元素进行上述比较，直到没有元素可比
源码
C/C++
void BubbleSort (std::vector<int> &vec)
{if (vec.size() <= 1) {return ;}int i, j;for (i = 0; i < vec.size(); ++i) {//外层循环控制边界for (j = 0; j < vec.size()-i-1; ++j) {if (vec[j+1] < vec[j]) {std::swap(vec[j], vec[j+1]);}}}
}
Python
def swap(sequence, i, j):temp = sequence[i]sequence[i] = sequence[j]sequence[j] = tempdef BubbleSort(sequence):n = len(sequence)while n > 1:i = 1while i < n:if sequence[i] > sequence[i-1]:swap(sequence, i, i-1)i += 1n -= 1
时间复杂度
在最好情况下，待排序序列已经按照指定顺序排好，此时只需要比较n-1次，没有交换次数，则这种情况下时间复杂度为O(n)；在最坏情况下，待排序序列反序排列，此时需要比较n(n-1)/2次，需要交换3n(n-1)/2次，故最坏时间复杂度为O(n?)。综上，冒泡排序的平均时间复杂度为O(n?)。
稳定性
冒泡排序就是把小元素一步步往前调或把大元素一步步往后调，对于相等元素一般不会交换（这样没有意义，对算法也没有影响），因此冒泡排序是稳定的。