在最坏情况下,堆排序需要比较的次数为【 】。

admin2009-03-15  44

问题 在最坏情况下,堆排序需要比较的次数为【  】。

选项

答案O(nlog2n)。

解析 堆排序的使用方法如下: (1)首先将一个无序序列建成堆; (2)然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素,只考虑前n-1个元素构成的子序列,显然,在子序列已经不是堆,但左、右子树仍为堆。反复做第2步,直到剩下的子序列为空为止。堆排序对于规模较小的线性表并不合适,但是对于大规模的线性表来说很有效。在最坏的情况下,堆排序需要比较O(nlog2n)次。
转载请注明原文地址:https://kaotiyun.com/show/uo7Z777K
0

最新回复(0)