- 比较中
- 已交换
- 已就位
冒泡排序
冒泡排序一遍又一遍地遍历列表,比较每对相邻的值,左边较大时就交换。每一趟结束后,尚未就位的最大值都会“冒”到末尾。你可以用任意速度播放,也可以逐次比较单步查看,同时观察比较次数、交换次数和趟数的计数。 按“播放”观看排序过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。卡片统计比较次数、交换次数和趟数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
- 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到排序的任意位置。
- 观察卡片上的比较次数、交换次数和趟数,并与最坏情况对比。
冒泡排序的原理
从左边开始。比较前两个值,如果左边较大就交换。向右移动一位再比较,直到列表末尾。这就是一趟,它会把最大值放到最后一位。下一趟提前一位结束。如此继续,直到某一趟没有交换,或只剩一个值。
计算工作量
对 n 个值,第一趟进行 n − 1 次比较,下一趟 n − 2 次,依此类推,所以完整排序最多进行 n(n − 1)/2 次比较。交换次数总是等于初始列表中的逆序对数,即顺序错误的值对。倒序列表最多,有 n(n − 1)/2 个。已排序的列表没有逆序对,开启提前停止时只需一趟、n − 1 次比较。
常见问题
为什么叫冒泡排序?
因为大的值会像水中的气泡一样升到列表末尾。每一趟中,尚未就位的最大值会一步步向右移动,直到到达最终位置。
冒泡排序要进行多少次比较和交换?
对 n 个值最多进行 n(n − 1)/2 次比较:10 个值 45 次,40 个值 780 次。交换次数总是等于初始列表中的逆序对数,从已排序列表的 0 次到倒序列表的 n(n − 1)/2 次。
提前停止有什么用?
如果整趟都没有交换,说明每对相邻值都已有序,列表已排好,排序可以停止。开启提前停止后,已排序的列表只需一趟。关闭后,冒泡排序总是进行全部 n − 1 趟。
实际中会用冒泡排序吗?
很少。它简单且稳定,但平均耗时与 n² 成正比。对于较短或基本有序的列表,插入排序完成同样的工作步骤更少;对于较长的列表,归并排序或快速排序要快得多。
我的数字会被发送到别处吗?
不会。排序在你的浏览器中运行,上次的设置保存在本浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器