堆排序算法的思路及C代码实现
1. 概念
堆排序(Heap Sort)是将待排序数组看成一颗完全二叉树的顺序存储,利用完全二叉树中双亲节点和孩子节点的关系,不断筛选其中的大(小)关键字不断上移的过程。
2. 代码思路(以大根堆为例)
- 设计一个算法
HeapAdjust
:使传入要重建为堆的根节点(一号),检查比较其与子元素的大小关系。如果子元素(三号)较大就使其上移,子节点(三号)位置不能用根节点元素(一号)补上,因继续以子节点(三号)为根节点往下继续调整为大根堆,直至其为叶节点。 - 设计一个算法
CreateHeap
:初始化无序树树为最大根堆。以i = n/2
的第一个非叶节点开始,传入HeapAdjust
进行局部重建大根堆,依次i--
直到根节点。 - 完整的算法
HeapSort
:-
- 先初始化树为最大根堆
-
- 将最大节点(根节点)与尾节点交换位置
-
- 此时破坏了大根堆特性,重新以根节点开始,局部重建大根堆
-
- 重复步骤2,3 (n-1)次,即可得到升序排列的次序
-
3. 完整代码参考(C语言)
#include <stdlib.h>
#define MAXSIZE 10 // 静态顺序表最大长度
typedef int ElemType; // 假设数据类型为int类
typedef struct { // 静态顺序表数据元素
ElemType data[MAXSIZE + 1]; // 数据项 [0]不放数据
int length;
}SqList;
void initList(SqList* L) { // 初始化顺序表
L->length = MAXSIZE;
for (int i = 1;i <= L->length;i++) {
L->data[i] = rand(); // 随机初始化数据
}
}
void printData(SqList* L) {
for (int i = 1; i <= L->length; i++) {
printf("%d ", L->data[i]);
}
puts();
}
void HeapAdjust(SqList* L, int k, int len) { // 将以k为根节点的子树调整为大根堆
L->data[0] = L->data[k]; // 暂存子树的根节点
for (int j = 2 * k;j <= len; j *= 2) { // 沿着k较大的子节点往下筛选
if (j < len && L->data[j] < L->data[j + 1]) // j<length 防止没有右节点
j++; // 将j指向节点较大的数组下标
if (L->data[0] >= L->data[j]) break; // 若根节点此时大于等于右节点,跳出循环
else {
L->data[k] = L->data[j];
k = j; // 将k重置为子树交换的节点,以便后续调整该节点为大根堆
}
L->data[k] = L->data[0];
}
}
void CreateHeap(SqList* L) { // 把无序列表建成大根堆
int len = L->length;
for (int i = len / 2;i > 0;i--) { // n/2为二叉排序树中最接近的叶节点的元素,依次往上扫描
HeapAdjust(L, i, len);
}
}
void HeapSort(SqList* L) { // 对顺序表进行堆排序
CreateHeap(L);
puts("第一次初始化大根堆:");
printData(L);
for (int i = L->length;i > 1;i--) { // 进行n-1次交换和重建堆过程
ElemType temp = L->data[i]; // 将最大(根元素)与表的最后一个元素交换
L->data[i] = L->data[1];
L->data[1] = temp;
HeapAdjust(L, 1, i - 1); // 重新把树整理为堆
printf("第%d次整理大根堆:\n", L->length - i + 1);
printData(L);
}
}
void main() {
SqList L;
initList(&L);
printData(&L);
HeapSort(&L);
}
4. 后记
实现了这个算法花了我三小时差不多时间,其中对C代码也不是很熟,写惯了JavaScript里面调用函数直接传入字符串就行,c语言里面却行不通,想往函数里面传入字符串不知道怎么穿,有大佬看见希望评论教我一下。好久没写博客,今天先水一期。