基本思路
从左到右遍历列表,查看每对相邻的值。如果左边的值比右边大,就交换它们。到达末尾时,最大值已被一路带到最后一位,就像气泡升到水面。这样的一次遍历叫作一趟。重复多趟,直到列表有序。
一个例子
以 5, 1, 4, 2, 8 为例。第一趟比较 5 和 1 并交换,然后比较 5 和 4(交换)、5 和 2(交换)、5 和 8(不交换):1, 4, 2, 5, 8。8 已到最终位置。第二趟比较 1 和 4(不交换)、4 和 2(交换)、4 和 5(不交换):1, 2, 4, 5, 8。第三趟没有任何交换,列表已排好:共 9 次比较、4 次交换。
为什么每一趟都多一个值就位
在一趟中,目前见到的最大值总会被一路带着走:一旦遍历到它,之后的每次比较都会把它向右移一位。所以第一趟把最大值放到最后,第二趟把第二大的值放在它前面,依此类推。第 k 趟之后,最后 k 个位置已确定,下一趟可以提前一位结束。这就是每趟越来越短的原因。
交换次数等于逆序对数
逆序对是顺序错误的一对值:较大的值排在较小的值之前。交换一对顺序错误的相邻值,恰好消除一个逆序对,且不会产生新的。所以无论比较的顺序如何,冒泡排序的交换次数都恰好等于初始列表的逆序对数。已排序的列表没有逆序对;n 个值的倒序列表有 n(n − 1)/2 个,是可能的最大值。
提前停止与开销
如果整趟都没有交换,说明每对相邻值都已有序,列表已排好。检查这一点后,冒泡排序只需一趟、n − 1 次比较就能处理完已排序的列表。最坏情况下仍需 n − 1 趟和 n(n − 1)/2 次比较,平均交换次数为 n(n − 1)/4。两者都随 n² 增长,所以列表长度翻倍,排序时间约变为四倍。
冒泡排序是稳定的:相等的值从不交换,因此保持原有顺序。它是原地排序,不需要额外内存。插入排序也有这些特性,且通常步骤更少;归并排序和快速排序的耗时与 n log n 成正比,在长列表上要少得多。
动手试试
打开应用并按“播放”,或按“单步”逐次比较。正在比较的两个值会高亮显示,交换用单独的颜色表示,已就位的值变为绿色。试试倒序列表看最坏情况,试试基本有序的列表看提前停止如何在几趟后结束排序,或者输入上面例子中的数字。
常见问题
冒泡排序的时间复杂度是多少?
最坏和平均情况下为 O(n²):n 个值最多 n(n − 1)/2 次比较。开启提前停止后,已排序的列表只需 O(n),即一趟。它只需要 O(1) 的额外内存。
冒泡排序是稳定的吗?
是的。只有当左边的值严格大于右边时才交换相邻值,所以相等的值不会互相越过,保持原有顺序。
冒泡排序和插入排序有什么区别?
两者都交换相邻值,交换次数也都等于逆序对数。冒泡排序对未排序部分进行完整的遍历;插入排序只把每个新值向前移动到需要的位置,所以通常比较次数更少,在基本有序的列表上尤其如此。
什么时候适合用冒泡排序?
主要用于教学,以及简单比速度更重要的极短列表。对于更大的数据,编程语言内置的排序要快得多。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试冒泡排序