一、算法介绍
1.算法思想
堆排序是指利用堆这种数据结果所设计的一种排序算法，堆排序也是选择排序的一种，只不过是通过堆来进行选择，其核心思想主要包括建堆和堆排序两步操作：
建堆：
‘首先要将所给定的序列在逻辑上看作是一棵完全二叉树，然后根据完全二叉树的特点，从完全二叉树倒数第一个非叶子节点开始，利用向下调整算法依次往前调整，这样就可以将完全二叉树调整为一个堆。
堆排序：
堆排序主要是利用堆删除的思想来进行排序：将堆顶与末尾位置进行交换，此时必然会破坏堆的结构，所以在交换后，需要重新对二叉树进行调整使之重新成为一个堆，但是交换后来的元素不会参与后续的调整，这里可以通过设置一个末尾标志位实现，没完成一次交换，末尾标志位向前移动一位，直到调整完整个序列，完成堆排序。
2.算法流程
注：根据堆的特性和堆排序的思想，排升序需要建大堆，排降序需要建小堆。
对于堆的相关知识及详细实现过程可以参考往期博客。
二、算法实现
1.代码实现
#include<stdio.h> #include<stdlib.h> //堆排序---->利用堆删除的思想来进行排序 升序：大堆 降序：小堆 void Test_HeapSort(); void HeapSort(int* array, int n);//堆排序 void AdjustDown(int* array, int parent, int size);//堆排序子函数->向下调整法 int Min(int num1, int num2);//降序--小堆 int Max(int num1, int num2);//升序--大堆 void Swap(int* parent, int* child);//交换双亲结点与孩子结点 void Printf_array(int* array, int length);//数组打印函数 int main() { Test_HeapSort(); return 0; } void Test_HeapSort() { int array[] = { 49, 27, 37, 65, 28, 34, 25, 15, 18, 19 }; int length = sizeof(array) / sizeof(array[0]); printf("排序前："); Printf_array(array, length); HeapSort(array, length);// 对数组进行堆排序 printf("\n排序后："); Printf_array(array, length); } void HeapSort(int* array, int n) {//堆排序 //1.建堆 for (int root = ((n - 1) - 1) / 2; root >= 0; root--) {//n-1为最后一个叶子结点的下标，root为该结点的双亲 AdjustDown(array, root, n);//向下调整 } //2.利用堆删除的思想来进行排序 int end = n - 1;//标记调整位置的最大下标 while (end) { int temp = array[0]; array[0] = array[end]; array[end] = temp; AdjustDown(array, 0, end); end--; } } void AdjustDown(int* array, int parent, int size) {//向下调整 int child = parent * 2 + 1;//标记左孩子 while (child < size) { if (child + 1 < size && Max(array[child + 1], array[child])) {//找左右孩子较小的孩子 child += 1; } if (Max(array[child], array[parent])) {//检测是否满足堆的特性 Swap(&array[parent], &array[child]);//不满足，交换并继续向下调整 parent = child; child = parent * 2 + 1; } else {//满足，直接返回 return; } } } void Swap(int* parent, int* child) {//整数交换 int temp = *parent; *parent = *child; *child = temp; } void Printf_array(int* array, int length) {//数组打印函数 for (int i = 0; i < length; i++) { printf("%d ", array[i]); } } int Min(int num1, int num2) {//降序--小堆 return num1 < num2; } int Max(int num1, int num2) {//升序--大堆 return num1 > num2; }
2.测试用例及结果
测试用例：
array[]={49，27，37，65，28，34，25，15，18，19}
测试结果：
三、性能分析
1.时间复杂度
根据算法排序思想，每次交换堆顶与末尾元素完成一个元素的排序之后都需要利用向下调整算法将二叉树重新调整为堆，而单次调整的时间复杂度为，所以对于n个元素，堆排序的时间复杂度为。
2.空间复杂度
由于算法中除了定义一些临时变量外，没有借助额外的辅助空间，所以堆排序的空间复杂度为O(1)。
3.稳定性
因为堆排序在元素交换时是隔着元素进行交换的，所以过程中会改变相同元素的相对位置，所以堆排序是不稳定的。
