显示堆排序重复比较

Question

如何证明堆排序重复了它以前所做的比较？（即它将执行以前完成的比较）谢谢

Answer 1

这两个元素可以在构建堆步骤（heapify）和堆排序的重新排序步骤中进行比较。这是维基。

例如，按最大堆排序：

• 源阵列：4 6 10 7 3 8 5
• heapify shift-up 的新堆数组。
  比较： 4<6， 6<10， 4<7， 6<8（10） （7 8） （4 3 6 5）//每层按括号分组
• 重新订购步骤
  将
  • 第一个与最后一个交换，将大的
  结束
  • 将堆大小减少 1
  • 使用shift-down
    比较：
  5<8， 6<7， 3<6， 3<4， 3<5， 3<4

因为，在heapify基于元素顺序的比较。heapify之后，订单也可能不排序。所以可能还有其他比较。