QQ登录

只需一步,快速开始

搜索
鱼C论坛笔记大赛成绩公示
查看: 69|回复: 1

堆排序算法看不明白的一处

[复制链接]
累计签到:1 天
连续签到:1 天
最佳答案
0 
发表于 2017-9-14 00:33:04 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 panzer111 于 2017-9-14 00:49 编辑

// 159.cpp : 定义控制台应用程序的入口点。
//
#include "StdAfx.h"
#include <stdio.h>
void swap(int k[],int i,int j)
{
        int temp;
        temp=k;
        k=k[j];
        k[j]=temp;
}
void HeapAdjust(int k[],int s, int n)
{
        int i;
        int temp=k;
        for(i=2*s;i<=n;i*=2)
        {
                if (i<n && k<k[i+1])
                {
                        i++;
                }
                if (temp >=k)
                {
                        break;
                }
                k=k;
                s=i;
        }
        temp=k;

}

void HeapSort(int k[],int n)
{
        int i;
        for(i=n/2;i>0;i--)
                HeapAdjust(k,i,n);
        for(i=n;i>1;i--)
        {        swap(k,1,i);
                HeapAdjust(k,1,i-1);

        }
}
int main()
{
        int i,a[10]={1,5,7,3,54,49,21,78,47,16};
        HeapSort(a,9);
        for(i=1;i<10;i++)
        {
                printf("%d",a);
        }
        return 0;
}
------------------
void HeapSort(int k[],int n)
{
        int i;
        for(i=n/2;i>0;i--)
                HeapAdjust(k,i,n);
        for(i=n;i>1;i--)
        {        swap(k,1,i);
                HeapAdjust(k,i,i-1);

        }
}
------------------
第一个for循环结束后,i已经到了0,首先从n/2开始构建堆,然后从n/2-1开始,自减直到1,也即是第一个起始数,那么第一个for循环结束后是否意味着对整个数组而言,HeapAdjust的整体大顶堆已经构建完毕?

既然整体大顶堆构建完毕,是指所有元素达到有序排列,还是仅仅把最大元素送上堆顶?
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
累计签到:1 天
连续签到:1 天
最佳答案
0 
 楼主| 发表于 2017-9-14 00:38:52 | 显示全部楼层
本帖最后由 panzer111 于 2017-9-14 00:52 编辑

如果第一个for循环后大顶堆已经完毕,说明从n/2开始,到起始节点的上一行的最右节点开始构建

也就是说总会从起始节点i的双亲i/4,i/8....直到1,开始构建

for循环完毕后整个堆已经是有序状态,直接输出即可,为何还要第二个for循环?
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-9-23 08:24 Powered by Discuz! X2.5 Theme by dreambred

快速回复 返回顶部 返回列表