前言
常见的排序算法有七种。
本篇文章将会详细介绍堆排序的实现。
一、什么是堆
所谓堆，就是一种特殊的完全二叉树。在堆当中，任何一个结点的值都要比其孩子要大或者小，任意结点都比其孩子大的叫做大堆（或大根堆），任意结点都比其孩子小的叫做小堆（或小根堆）。
二、堆在数组中的存储
由于堆是一个完全二叉树，而完全二叉树从根结点到最后一个结点之间是没有空值的，是一种非常连续的结构。所以我们大多数情况下都是使用顺序存储在数组当中。
堆，或者说二叉树在数组中都是一层一层、从左往右存储的。根结点的下标为 0 。
需要注意的是，根据上图，我们可以找到一个规律，这个规律在堆当中是蛮重要的。假设某一个结点的下标是 i ，那么它的父结点（假如存在）的下标就是 （i - 1） / 2 ，它的左孩子（假如存在）的下标就是 i * 2 + 1 ，它的右孩子（假如存在）的下标就是 i * 2 + 2。所以在数组当中，我们可以根据以上规律很快的找到任意结点的父结点或者子结点。
三、堆排序思想
想要理解堆排序只需要理解两个部分即可。1.求出当前最值 ， 2.调整，剩下就不断重复以上两个步骤，直到排好序即可。
1.求出当前最值
当我们了解堆的概念以及性质后，我们会很轻松的知道，堆的任意一个结点都是以该结点为根结点的子树中的最值，而整个堆的根结点，也就是堆顶元素，是整个堆的最值。
真的是太明显了，这个堆的当前最值是什么？当然是根结点啦。问题是我们该如何获取到这个最值？直接取吗？然后删除这个根结点？那谁做新的根结点？左孩子？右孩子？所以说这是行不通的，我们在上面已经讲了，堆在内存中一般以数组的方式存储，你让所有数据整体左移一个单位，那堆的结构就全乱套了。
正确做法是，将根结点与堆的尾结点进行交换，然后再删除已经是最值的尾结点，最后新的根结点向下调整，直到符合堆的结构为止。
2.调整
在取得了当前的最值后，原本的尾结点已经被移动到了根结点，此时根结点的位置不一定是它应该在的地方，它应该不断与其孩子比较，使其符合堆的结构，当它并没有与孩子交换时，说明已经调整完成，一个新的堆出现了。
当完成这一步后，就可以接着重复以上两个步骤，直到排好序。
需要注意的是，我们每次都能将当前最值排好序到数组末尾，如果是大堆，则最大值在末尾，如果是小堆，则最小值在末尾。也就是说 建大堆会排成升序，建小堆会排成降序。
四、代码实现
1.库函数头文件及声明
#include<stdio.h> #include<stdlib.h> #include<assert.h> // 宏定义数据类型 typedef int HPDataType; // 堆结构体 typedef struct Heap { // 指向数组的指针 HPDataType* a; // 堆的有效数据个数 int size; // 堆的容量 int capacity; }HP; // 堆的初始化 void HeapInit(HP* php); // 堆的销毁 void HeapDestroy(HP* php); // 向下调整 void AdjustDown(HPDataType* a, int size, int parent); // 交换函数 void Swap(HPDataType* a, HPDataType* b);
2.其他函数实现
// 堆的初始化 void HeapInit(HP* php) { // php指向堆结构体，为空说明堆没有创建，传参错误 assert(php); // 指向数组的指针初始指向空 php->a = NULL; // 堆的有效数据初始为0 php->size = 0; // 堆的容量初始为0 php->capacity = 0; } // 堆的销毁 void HeapDestroy(HP* php) { assert(php); // 释放数组空间 free(php->a); // 释放空间后指针置空 php->a = NULL; // 回归默认状态 php->size = 0; // 回归默认状态 php->capacity = 0; } // 交换函数 void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } // 向下调整函数 void AdjustDown(HPDataType* a, int size, int parent) { // 父结点的左孩子 int child = parent * 2 + 1; // 左孩子存在（父结点不是叶子结点） while (child < size) { // 找出左右孩子中的小值 if (child + 1 < size && a[child + 1] < a[child]) ++child; // 左右孩子的最小值比父亲要小，则跟父结点交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); // 更新父结点的下标 parent = child; // 更新左孩子的下标 child = parent * 2 + 1; } // 不需要交换则说明堆的结构已成，直接退出 else break; } }
3.堆排序函数
void HeapSort(HPDataType* arr, int len) { // 创建堆 HP hp; // 初始化堆 HeapInit(&hp); // 建堆，当前是小堆 for (int i = len; i >= 0; --i) { AdjustDown(arr, len, i); } // end是末尾元素的下标 int end = len - 1; while (end > 0) { // 将最小值交换到堆的末尾 Swap(&arr[0], &arr[end]); // 堆顶元素重新向下调整 AdjustDown(arr, end, 0); // 每排好一个数据让end-1 --end; } }
4.主函数
int main() { // 测试数组 int arr[] = { 416,684,654,516,156,83,941,3584,164,168,51,53,49,849,764 }; // 数组大小 int i = sizeof(arr) / sizeof(arr[0]); // 堆排序 HeapSort(arr, i); // 打印排好序的数组 for (int j = 0; j < i; ++j) printf("%d ", arr[j]); printf("\n"); return 0; }
5.结果演示
五、复杂度分析
1.时间复杂度
在堆排序中，排好一个数据只需要两步，交换和向下调整。交换花费的时间及其少，忽略不计。向下调整中，我们发现，每次调整都会让结点往下移动一层，最多移动 总层数 - 1 次，我们知道，二叉树的层数与数据个数是 log2 n 级别的。所以每排好一个数据花费的时间是 log2 n 级别的，当有 n 个数据时，堆排序排好的时间复杂度就是 O(N * log2 N) 。
2.空间复杂度
是的，我们没有开辟额外数组空间，所以空间复杂度是 O(1) 。
六、提一嘴
在建堆的时候，我使用了向下调整建堆，我没有做详细说明，这个读者可以下去自行画图理解理解。不仅仅是向下调整可以建堆，向上调整也可以建堆，这两种方法读者都可以尝试。再多就不是堆排序的内容了，感兴趣的可以看看堆的实现。
总结
本篇文章详细介绍了堆排序的实现，作为排序速度最快的那一档，还是非常有必要学习掌握的。制作不易，还请读者三连支持一下，您的鼓励是我创作的动力，谢谢。
