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;
}