以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  问一个对排序的比较次数问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=55567)

--  作者：xiuluodao
--  发布时间：11/18/2007 10:53:00 PM

--  问一个对排序的比较次数问题
第7章32题中说用堆排序执行序列
｛503,017,512,908,170,897,275,653,612,154,509,612,677,765,094｝
答案上说：建堆要比较（2*4）+（2*1+2*2）+（2*1+2*1+2*1）＝20次
有没有谁能解释一下为什么这么算，要熄灯了，只能打这么多了！
--  作者：zewixi
--  发布时间：11/19/2007 4:26:00 PM

--  
初始数组的树形结构如下：
                  503
                 /  \
                /    \
               /      \
              /        \
             /          \
            /            \
           /              \
          /                \
        017                 512
       /   \               /   \
      /     \             /     \
     /       \           /       \
   908       170       897       275
  /  \      /  \      /  \      /  \
/    \    /    \    /    \    /    \
653  612  154  509  612  677  765  094
--  作者：zewixi
--  发布时间：11/19/2007 4:41:00 PM

--  
1、每个3结点的单位子树（根结点和左右子结点）按照SiftDown算法调整成堆需要且只需要比较2次（先是左右子结点比较选出较小者，然后较小者再与根结点比较）；
2、第2层（根为第0层）4棵子树调整成堆，需要比较2*4次；第3层的094和154被交换到了第2层；
3、第1层2棵子树调整成堆，右边的那棵需要将094往上调，故需要2次对单位子树进行建堆，所以需要比较2*2次；而左边那棵，由于根结点017显然是整棵子树的最小值了，故已经是堆了，只需要1次对单位子树进行建堆，比较2*1次；
4、同理分析根结点503，它显然是往右子树下调，观察各值，503会被调整到叶结点去，需要进行3次单位子树建堆，比较2*3＝2*1+2*1+2*1次；
所以总次数为
（2*4）+（2*1+2*2）+（2*1+2*1+2*1）＝20次
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 35.156ms