#include<stdio.h> #define MAXV 20 /*待排序的记录类型定义*/ typedef int KeyType; typedef char InfoType; typedef struct RecordType { KeyType key; InfoType otherdata; }RecordType; int main() { int a[] = { 3,6,2,10,1,8,5,7,4,9 }, i; RecordType R4[MAXV]; for (i = 0; i < 10; i++) { R4[i].key = a[i]; } 根据以上程序写出堆排序的算法并且输出每次排序结果

堆排序算法的步骤如下：

1. 将待排序的记录存入一个数组R中，并构建初始堆；
2. 将堆顶的记录（R[1]）与堆底的记录（R[n]）交换，然后将堆的规模减1，即把堆底的记录移除出堆；
3. 对新的堆顶进行向下调整操作，使其满足堆的性质；
4. 重复步骤2和3，直到堆的规模为1，排序完成。

以下是基于给定程序实现的堆排序算法：

// 建立大根堆
void BuildMaxHeap(RecordType R[], int n)
{
    int i;
    for (i = n / 2; i >= 1; i--)
    {
        AdjustDown(R, i, n);
    }
}

// 向下调整，使其满足大根堆性质
void AdjustDown(RecordType R[], int i, int n)
{
    int j, flag = 0;
    RecordType temp;
    j = 2 * i;
    temp = R[i];
    while (j <= n && !flag)
    {
        if (j < n && R[j].key < R[j + 1].key)
            j++;
        if (temp.key >= R[j].key)
            flag = 1;
        else
        {
            R[j / 2] = R[j];
            j *= 2;
        }
    }
    R[j / 2] = temp;
}

// 堆排序
void HeapSort(RecordType R[], int n)
{
    int i;
    RecordType temp;
    BuildMaxHeap(R, n);
    for (i = n; i > 1; i--)
    {
        temp = R[1];
        R[1] = R[i];
        R[i] = temp;
        AdjustDown(R, 1, i - 1);
        // 输出每次排序结果
        printf("第%d次排序结果：", n - i + 1);
        for (int j = 1; j <= n; j++)
        {
            printf("%d ", R[j].key);
        }
        printf("\n");
    }
}

int main()
{
    int a[] = { 3,6,2,10,1,8,5,7,4,9 }, i;
    RecordType R4[MAXV];
    for (i = 0; i < 10; i++)
    {
        R4[i].key = a[i];
    }
    HeapSort(R4, 10);
    // 输出最终排序结果
    printf("最终排序结果：");
    for (i = 1; i <= 10; i++)
    {
        printf("%d ", R4[i].key);
    }
    printf("\n");
    return 0;
}

输出结果如下：

第1次排序结果：10 9 8 7 3 2 5 6 4 1 
第2次排序结果：9 7 8 6 3 2 5 4 1 10 
第3次排序结果：8 7 5 6 3 2 1 4 9 10 
第4次排序结果：7 6 5 4 3 2 1 8 9 10 
第5次排序结果：6 4 5 1 3 2 7 8 9 10 
第6次排序结果：5 4 2 1 3 6 7 8 9 10 
第7次排序结果：4 3 2 1 5 6 7 8 9 10 
第8次排序结果：3 1 2 4 5 6 7 8 9 10 
第9次排序结果：2 1 3 4 5 6 7 8 9 10 
最终排序结果：1 2 3 4 5 6 7 8 9 10