比较
交换
已取出

  • 下沉中
  • 比较中
  • 已交换
  • 已就位

更多关于堆排序

堆排序

堆排序把列表看作一棵二叉树,并将它整理成最大堆,即每个父节点都不小于它的子节点。这样最大值就在顶端。把它交换到末尾并固定下来,修复堆,然后重复。应用在柱子上方把堆画成一棵树,你可以跟着每个值看它如何下沉。 按“播放”观看排序过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。柱子上方的树以堆的形式显示相同的值。卡片统计比较次数、交换次数和从堆中取出的值的个数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
  2. 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到排序的任意位置。
  3. 观察这棵树:先是每个父节点下沉,直到堆建好;然后根节点被交换到末尾,堆缩小一个。

堆排序的原理

把列表看作一棵树:位置 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 — 无需安装,无需信用卡即可启动。

前往编辑器