在最坏情况下,堆排序需要比较的次数为多少?
问题描述：
在最坏情况下,堆排序需要比较的次数为多少?
一道全国计算机二级VF试题,
答
0（nlog2n）
首先前面的那个是O而不是0,相信你应该了解时间复杂度的表示方法吧,前面就有一个O,我认为此处也应该是和那个一样的含义,即取n的最大次方!下面我们看看堆排序的定义：
n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤[n/2] )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字.堆排序的特点是：在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】,在当前无序区中选择关键字最大(或最小)的记录.
看完之后相信你自己就可以解答自己的疑问了!