C语言实现堆排序

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#include<string.h>
// 定义元素类型为整型
typedef int ElemType;

// 定义静态表结构体
typedef struct{
    ElemType *elem;        // 动态分配的数组指针
    int TableLen;          // 表长度
} SSTable;

// 初始化静态表
void STInit(SSTable &ST, int len) {
    ST.TableLen = len;     // 设置表长度
    ST.elem = (ElemType *)malloc(sizeof(ElemType)*ST.TableLen); // 分配内存
    int i;
    srand(time(NULL));      // 使用当前时间作为随机数种子
    for(i = 0; i < ST.TableLen; i++){ // 循环初始化数组元素
        ST.elem[i] = rand()%100;      // 随机填充元素（0-99）
    }
}

// 打印静态表内容
void STPrint(SSTable ST){
    for(int i = 0; i < ST.TableLen; i++){
        printf("%3d",ST.elem[i]); // 打印元素，右对齐，总宽度为3个字符
    }
    printf("\n");                 // 换行
}

// 交换两个元素的值
void swap(ElemType &a, ElemType &b){
    ElemType temp;               // 创建临时变量
    temp = a;                    // 保存第一个元素
    a = b;                       // 将第二个元素赋给第一个
    b = temp;                    // 将临时变量中的值（原第一个元素）赋给第二个
}

// 调整堆，使得子树满足最大堆性质
void AdjustDown(ElemType A[], int k, int len) {
    int dad = k; // 父节点的索引
    int son = 2 * dad + 1; // 左子节点的索引
    
    // 当子节点在数组范围内时进行调整
    while (son < len) {
        // 如果右子节点存在并且比左子节点大，则定位到右子节点
        if (son + 1 < len && A[son] < A[son + 1]) {
            son++;
        }
        
        // 如果子节点大于父节点，则交换它们
        if (A[son] > A[dad]) {
            swap(A[son], A[dad]);
            dad = son; // 更新父节点索引
            son = 2 * dad + 1; // 更新子节点索引
        } else {
            break; // 子节点不大于父节点时，停止调整
        }
    }
}

// 堆排序函数
void HeapSort(ElemType *A, int len) {
    int i;
    
    // 构建初始最大堆
    for (i = len / 2 - 1; i >= 0; i--) {
        AdjustDown(A, i, len); // 从最后一个非叶子节点开始向下调整
    }
    
    // 排序过程
    swap(A[0], A[len - 1]); // 交换最大元素到正确的位置（数组末尾）
    
    // 重复调整堆并将当前最大元素移到已排序区域
    for (i = len - 1; i > 1; i--) {
        AdjustDown(A, 0, i); // 重新调整堆，不包括已排序的元素
        swap(A[0], A[i - 1]); // 交换最大元素到正确的位置
    }
}

int main(){
    SSTable ST;
    STInit(ST,10);              // 初始化静态表，设置长度为10
    //ElemType A[10]={3,87,2,93,78,56,61,38,12,40};
    //memcpy(ST.elem,A,sizeof(A));
    STPrint(ST);                // 打印未排序的静态表
    HeapSort(ST.elem,10);     // 调用堆排序函数，对静态表中的数据进行排序
    STPrint(ST);                // 再次打印静态表，这次是排序后的结果
    scanf("%d");                // 防止程序立即退出
    return 0;
}