大家好，又见面了，我是你们的朋友全栈君。

堆排序

1. 算法思想

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

2. 实现原理

要实现从小到大的排序，就要建立大顶堆，即父节点比子节点都要大。

2.1、初始化数组，创建大顶堆。
	1. 大顶堆的创建从下往上比较，不能直接用无序数组从根节点比较，否则有的不符合大顶堆的定义。
2.2、交换根节点和倒数第一个数据，现在倒数第一个数据就是最大的。
2.3、重新建立大顶堆。
	1. 因为只有 array[0] 改变，其它都符合大顶堆的定义，所以可以根节点 array[0] 重新建立。
2.4、重复2.2、2.3的步骤，直到只剩根节点 array[0]，即 i=1。

3. 动态演示

网上这个就展示的非常好

我再用图片稍微解释一下。
原始数据：array[]={49,38,65,97,76,13,27,49,10}
原始堆排序
创建大顶堆
从倒数第二行往上比较父节点和子节点（即从数据一半开始向前运算），把大的往上移动，小的向下移，直到符合大顶堆定义。
交换根节点和最后一个节点

重新创建大顶堆
接下来就一直循环即可得到堆排序结果

4. 完整代码

五个函数
交换函数：void swap(int array[],int x,int y)
初始化大顶堆函数：void BuildHeap(int array[],int size)
生成大顶堆函数：void Down(int array[],int i,int n)
排序函数：void heapSort(int array[],int size)
主函数：int main()

#include <stdio.h>
void display(int array[], int size) { 

for (int i = 0; i < size; i++) { 

printf("%d ", array[i]);
}
printf("\n");
}
void swap(int array[], int x, int y) { 

int key  = array[x];
array[x] = array[y];
array[y] = key;
}
// 从大到小排序
// void Down(int array[], int i, int n) { 

// int child = 2 * i + 1;
// int key = array[i];
// while (child < n) { 

// if (child + 1 < n && array[child] > array[child + 1]) { 

// child++;
// }
// if (key > array[child]) { 

// swap(array, i, child);
// i = child;
// } else { 

// break;
// }
// child = child * 2 + 1;
// }
// }
// 从小到大排序
void Down(int array[], int i, int n) { 
 // 最后结果就是大顶堆
int parent = i;                    // 父节点下标
int child  = 2 * i + 1;            // 子节点下标
while (child < n) { 

if (child + 1 < n && array[child] < array[child + 1]) { 
 // 判断子节点那个大，大的与父节点比较
child++;
}
if (array[parent] < array[child]) { 
 // 判断父节点是否小于子节点
swap(array, parent, child);     // 交换父节点和子节点
parent = child;                 // 子节点下标 赋给 父节点下标
}
child = child * 2 + 1; // 换行，比较下面的父节点和子节点
}
}
void BuildHeap(int array[], int size) { 

for (int i = size / 2 - 1; i >= 0; i--) { 
 // 倒数第二排开始, 创建大顶堆，必须从下往上比较
Down(array, i, size);                 // 否则有的不符合大顶堆定义
}
}
void HeapSort(int array[], int size) { 

printf("初始化数组：");
BuildHeap(array, size); // 初始化堆
display(array, size);   // 查看初始化结果
for (int i = size - 1; i > 0; i--) { 

swap(array, 0, i); // 交换顶点和第 i 个数据
// 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
Down(array, 0, i); // 重新建立大顶堆
printf("排序的数组：");
display(array, size);
}
}
int main() { 

int array[] = { 
49, 38, 65, 97, 76, 13, 27, 49, 10};
int size    = sizeof(array) / sizeof(int);
// 打印数据
printf("%d \n", size);
printf("排序前数组：");
display(array, size);
HeapSort(array, size);
return 0;
}

5. 结果展示

（显示每次排序结果）
从小到大
从大到小

6. 算法分析

时间复杂度：

1. 最好：O(n log n)
2. 最坏：O(n log n)
3. 平均：O(n log n)

空间复杂度：O(1)

稳定性：不稳定