8644 堆排序

Description

用函数实现堆排序，并输出每趟排序的结果

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

第一行：初始建堆后的结果
其后各行输出交换堆顶元素并调整堆的结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

9 7 8 6 4 3 2 5 0 1        
8 7 3 6 4 1 2 5 0 9
7 6 3 5 4 1 2 0 8 9
6 5 3 0 4 1 2 7 8 9
5 4 3 0 2 1 6 7 8 9
4 2 3 0 1 5 6 7 8 9
3 2 1 0 4 5 6 7 8 9
2 0 1 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

#include<stdio.h>

int a[1000], n;
//从下标为1开始存储
void print() {
    for(int i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void heapadjust(int parent,int N) {
    int max, lchild, rchild;
    lchild = 2 * parent;//左孩子
    while(lchild<=N)//左孩子等于N时也能进循环，否则会少判断只有一个左孩子的情况
    {
        max=lchild;//先让最大值下标为左孩子
        rchild = lchild + 1;//右孩子
        if(rchild<=N && a[lchild]<a[rchild])//如果右孩子存在，比较左右孩子
        {
            max=rchild;//max的值是左右孩子中大的那个
        }
        if(a[parent]>a[max])//如果父节点比孩子节点最大的那个大
        {
            return ;//不用调整，下一个
        }
        else        //否则
        {
            int temp=a[parent];//交换父节点和大的那个孩子节点
            a[parent]=a[max];
            a[max]=temp;
            parent=max;//如果大孩子也有孩子，原父节点换到这里后可能不符合大根堆，需要循环继续调整
            lchild=parent*2;//大孩子的左孩子下标（如果<=N才能继续循环）
        }
    }
}
// 初始化大顶堆
void heapsort() {
    for(int i = n / 2; i >= 1; i--) { //下标1开始存储的最后一个非叶子结点为n/2
        heapadjust(i,n);
    }
    print();

    for(int i = n; i > 1; i--) {//注意循环的条件是i>1，i=1时就剩一个了，不用再调
        int temp = a[1];
        a[1] = a[i];
        a[i] = temp; // 交换
        heapadjust(1,i-1); // 调整堆的时候只用从根节点开始，因为交换第一个和最后一个不影响其他
        print();
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <=n; i++) {
        scanf("%d", &a[i]);
    }
    heapsort();
    return 0;
}

这个题主要是注意heapadjust函数怎么写