数据结构与算法之堆排序

小根堆--向下构建

#include<stdio.h>

int a[101],n;

void swap(int i,int t)
{
    int temp;

    temp = a[i];
    a[i] = a[t];
    a[t] = temp;
}

//向下构建
void siftdown(int i)
{
    int flag=0,t;

    while(flag==0&&2*i<=n)//表示存在结点
    {
        if(a[i]>a[2*i])//比左结点大
        {
            t = 2*i;
        }
        else
        {
            t = i;
        }

        if(2*i+1<=n)//表示存在右节点
        {
            if(a[t]>a[2*i+1])//此处容易出错！是a[t]而不是a[i],自己想想为什么！最经典部分之一
            {
                t = 2*i + 1;
            }
        }

        if(t!=i)
        {
            swap(i,t);
            i = t;//这一句，我认为是堆排序最经典的部分之二。
        }
        else
        {
            flag = 1;
        }
    }
}

void creat()
{
    int i;

    for(i=n/2;i>=1;i--)//堆排序最经典之3
    {
        siftdown(i);
    }
}

int deletemax()
{
    int t;

    t = a[1];
    a[1] = a[n];
    n--;        //堆排序最经典之4
    siftdown(1);

    return t;
}
int main()
{
    int i,num;

    printf("请输入堆中元素个数：");
    scanf("%d",&num);
    n = num;

    //对堆进行初始化
    printf("请输入待排序的元素：");
    for(i=1;i<=num;i++)
    {
        scanf("%d",&a[i]);
    }

    creat();//创建堆（其实就是对堆进行排序）

    printf("使用堆排序后:\n");
    for(i=1;i<=num;i++)//此处不要写成n了
    {
        printf("%d ",deletemax());
    }
    printf("\n");

    return 0;
}

大根堆--向上构建

#include<stdio.h>

int a[101],n;

void swap(int i,int t)
{
    int temp;

    temp = a[i];
    a[i] = a[t];
    a[t] = temp;
}

//堆排序的核心代码
void siftup(int i)
{
    int flag=0;
    while(i!=1 && flag==0)
    {
        if(a[i]>a[i/2])//比父结点大
        {
            swap(i,i/2);
        }
        else
        {
            flag = 1;
        }
                
        i = i/2;//继续向上调整
    }
}

void creat()
{
    int i;

    for(i=n;i>=1;i--)//堆排序最经典之3
    {
        siftup(i);
    }
}

void siftdown(int i)
{
    int flag=0,t;

    while(flag==0&&2*i<=n)//表示存在结点
    {
        if(a[i]<a[2*i])//比左结点小
        {
            t = 2*i;
        }
        else
        {
            t = i;
        }

        if(2*i+1<=n)//表示存在右节点
        {
            if(a[t]<a[2*i+1])//此处容易出错！是a[t]而不是a[i],自己想想为什么！最经典部分之一
            {
                t = 2*i + 1;
            }
        }

        if(t!=i)
        {
            swap(i,t);

            i = t;//这一句，我认为是堆排序最经典的部分之二。
        }
        else
        {
            flag = 1;
        }
    }
}

int deletemax()
{
    int t;

    t = a[1];
    a[1] = a[n];
    n--;        //堆排序最经典之4
    siftdown(1);

    return t;
}

int main()
{
    int i,num;

    printf("请输入堆中元素个数：");
    scanf("%d",&num);
    n = num;

    //对堆进行初始化
    printf("请输入待排序的元素：");
    for(i=1;i<=num;i++)
    {
        scanf("%d",&a[i]);
    }

    creat();//创建堆（其实就是对堆进行排序）

    printf("使用堆排序后:\n");
    for(i=1;i<=num;i++)
    {
        printf("%d ",deletemax());
    }
    printf("\n");

    return 0;
}

不要误解，其实无论向上调整还是向下调整都是可以构建大根堆或者小根堆的。
注：堆排序并不能保证完全有序，输出时需要不断调整才行！