基本过程

• 从第一个元素开始，每个元素都和其后的元素进行比较，如果它大于其后的元素，则进行交换，因此经过第一趟排序之后，最大的元素会被交换到最后一个位置上

• 按照上面的方式，将第二大的元素交换到倒数第二个位置上，如此循环，一直到将倒数第 2 大的元素交换到第 2 个位置上

• 如果在某趟排序中，没有发生元素交换，说明整个序列已经有序，可以退出排序

Python 实现

tim-chow 的 Github

时间复杂度

冒泡排序中的基本操作是交换元素。在最好的情况下，也就是序列直接有序，那么时间复杂度是 O(n)；在最坏的情况下，也就是序列是倒序的，那么时间复杂度是：

T(n) = (n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2 = n2 - n / 2

所以，时间复杂度是 O(n2)

空间复杂度

冒泡排序除了在交换数据元素时，用到了一个临时变量外，没有申请其它空间，所以空间复杂度是：O(1)。