非唯一元素上的堆排序算法复杂性

Question

我想知道堆排序如何在具有统一元素的数组上工作。我是在复杂性和跑步的背景下说话的。

Answer 1

在这种情况下，具有统一元素的数组是最佳情况的一个实例，因此复杂性将是O（n*log（n））（源）

这是理论上的。

当然，在实践中，您会注意到与平均情况（具有相同的复杂性）相比有所改进，因为您不再需要在元素之间进行交换。

如果你想亲眼看看改进有多大，我建议实现该算法，并在最佳、最差和平均情况下尝试。

祝你好运。