- 下沉中
- 比较中
- 已交换
- 已就位
堆排序
堆排序把列表看作一棵二叉树,并将它整理成最大堆,即每个父节点都不小于它的子节点。这样最大值就在顶端。把它交换到末尾并固定下来,修复堆,然后重复。应用在柱子上方把堆画成一棵树,你可以跟着每个值看它如何下沉。 按“播放”观看排序过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。柱子上方的树以堆的形式显示相同的值。卡片统计比较次数、交换次数和从堆中取出的值的个数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
- 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到排序的任意位置。
- 观察这棵树:先是每个父节点下沉,直到堆建好;然后根节点被交换到末尾,堆缩小一个。
堆排序的原理
把列表看作一棵树:位置 i 上的值,其子节点在位置 2i + 1 和 2i + 2。从最后一个父节点开始,把每个父节点下沉,建成最大堆:只要一个值小于它较大的子节点,两者就交换。当根节点存放最大值时,把它与堆的最后一个值交换。这个值就此固定,堆缩短一个,新的根节点下沉,使它重新成为堆。重复直到堆为空。
始终 n log n,原地排序
这棵树约有 log₂ n 层,所以每次下沉最多约 2 log₂ n 次比较,而建堆不到 2n 次。因此堆排序最坏情况约需 2n log₂ n 次比较,且不需要缓冲区:40 个值最多 352 次。它不像快速排序那样有糟糕的输入,也不像归并排序那样需要额外内存。实际中它通常比两者都慢,因为它在列表中来回跳跃,而且它不稳定。
常见问题
堆排序是如何工作的?
它把列表变成最大堆,即存放在列表中的一棵树,每个父节点都不小于它的子节点。然后反复把位于根节点的最大值交换到堆的末尾,再把新的根节点下沉以修复堆。
什么是堆?
一棵存放在列表中、不用指针的完全二叉树:位置 i 的子节点是位置 2i + 1 和 2i + 2。在最大堆中,每个父节点都不小于它的子节点,所以最大值总在根节点,即位置 0。
为什么建堆很快?
大多数值都靠近树的底部,只能下沉一两层。把各层的工作量加起来,整个建堆过程少于 2n 次比较,而不是 n log n。
堆排序稳定吗?
不稳定。把根节点交换到末尾会让值移动很远,所以相等的值可能改变顺序。
我的数字会被发送到别处吗?
不会。排序在你的浏览器中运行,上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器