一，引言
堆排序作为一种不局限于数组的排序，在实践中有这非同寻常的意义，为此学好堆排序的底层原理和代码实现是非常重要的，下面从向上调整算法，向下调整算法，堆排序，时间复杂度，空间复杂度和稳定性等方面进行分析：
二，向下调整算法--假设建小堆
1，函数原型：
void HeapSort(int* p, int bit, int tail);
第一个参数数组地址，第二个参数数组个数，第三个参数父亲节点的位置。
2，代码逻辑：
下面看一下随机的一组数据：
该数组以完成二叉树的形式展示如图：
首先第一步找一个非叶子节点（9）做为一个子树进行排序；
父亲节点和孩子节点进行比较，首先判断有没有右孩子节点，若存在右孩子节点，进行左右孩子进行比较取小值，取较小值与父亲节点进行比较，若该节点小于父亲节点进行交换。第一轮排序结束。其结果保证该子树单独为堆。
第二趟排序：
选择前一个节点进行第二次排序如图：
因为父亲节点小于两个孩子节点所以不需要进行交换。
此时该二叉树如图：
再选择前一个节点4，进行相同排序第一趟如图：
此时孩子节点下方还有节点还需要继续进行比较，交换后的4变成新的父亲节点，与下方的孩子节点进行比较，结果如图：
每次比较的方法个第二步都相同，直到孩子节点为最后一个节点则比较结束。
总结：为此看函数模型的第二个参数根据数据个数可以得出最后一个节点，第三个参数传入父亲节点，通过函数循环依次的调取每一个非叶子节点（9--2--1）根据函数节点个数判断结束条件。
代码实现：
void HeapSort(int* p, int bit, int tail)
{
assert(p);
int parent = tail;
int child = parent * 2 + 1;
while (child < bit)
{
if (child + 1 < bit)
{
if (p[child] > p[child + 1])
{
child++;
}
}
if (p[child] < p[parent])
{
swap(&p[child], &p[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}三，堆排序
推排序就是首先通过建堆算法对一个数组进行建堆，之后通过第一个数据和最后一个数据进行交换，之后通过向下调整算法，重新构成一次次小的堆，依次往复最终使得该数组变成有序。
代码实现如下：
int main()
{
int arr[] = { 4,2,9,8,7,13,1};
int a = (6 - 1) / 2;
for (int i = a; i >= 0; i--)
{
HeapSort(arr, 7, i);
}
for (int j = 6; j > 0; j--)
{
swap(&arr[0], &arr[j]);
HeapSort(arr, j, 0);
}
return 0;
}第一个for循环进行建堆算法，这个方法有很多，具体可以参考数据结构---堆中有讲解。第二个for循环进行排序。这里需要注意小堆是降序，大堆是升序。
四，时间复杂度：
这里的时间复杂度注意分析建堆和向下调整的时间复杂度具体·如图：
而向下调整相当于每个节点最多进行高度次的调整。因此是N*log^N.
综上堆排序的时间复杂度为N*log^N。
五，空间复杂度
因没有开辟新的空间因此为O（1）.
六，稳定性
堆排序为不稳定排序，在不断的调整相同数据会变成变换。