1.堆排序：堆排序是按照堆的数据结构来进行排序 并且这种数据结构称为完全二叉树。
大顶堆：父节点值大于孩子节点 升序排列用大顶堆
小顶堆：父节点值小于孩子节点 降序排列用小顶堆
2.堆排序原则：
将数组先臆想成二叉树，然后调整为大顶堆，接着向根节点的值和尾结点进行交换，交换完毕将当前根节点排除我们整个排序过程，直到二叉树只剩下一个节点，具体原则流程见下图：
3.堆排序代码实现
补充：推子节点和父节点关系 如果父节点下标是i 则子节点下标是2i+1
子节点下标是i 父节点下标是(i-1）/2
void Heap_Adjust(int* arr, int len, int start, int end)
{
//将start这个下标的值 拷贝到tmp
int tmp = arr[start]; //难点4：i=start*2+1
for (int i = start * 2 + 1; i <= end; i = start * 2 + 1)//i代表左孩子的下标
{
if (i + 1 <= end && arr[i + 1] > arr[i]) //i+1代表右孩子下标
{ //如果左右孩子都存在，且右孩子的值大于左孩子，则让i指向右孩子
i++;
}
//此时i肯定指向较大的孩子节点
if (arr[i] > tmp)//较大孩子的值 还大于 父节点的值
{
arr[start] = arr[i];
start = i; //难点5：start要指向新的空白格子
}
else
{
break;
}
}
arr[start] = tmp; //难点6： 什么时候将tmp放回数组？
//两种情况： 1.空白格子没有孩子节点
// 2.有孩子节点，但是孩子节点值小于tmp
}
//堆排序
void Heap_Sort(int* arr, int len) //单独Heap_Sort是O(n)
{
//从最后一个非叶子节点开始，由内到外开始调整 //难点1：(len-1-1)/2理解： 子节点是len-1 其父节点是(len-1-1)/2
for (int i = (len - 1 - 1) / 2; i >= 0; i--)//i保存非叶子节点的下标
{ //难点3 len-1（饱和式救援)
Heap_Adjust(arr, len, i, len-1);//这里，第四个参数end没有规则，因为每次调整的那个小框的最后一个子节点下标无法确定 所以直接给尾结点下标len-1即可
}
//将顶部根节点的值（0号下标）和当前最后一个节点值（len-1-i号下标）进行交换
for (int i = 0; i < len - 1; i++)
{
int tmp = arr[0];
arr[0] = arr[len - 1 - i];
arr[len - 1 - i] = tmp;
//这里，调整只需要一次即可（最外面的框） 难点2：(len-1-i)-1
Heap_Adjust(arr, len, 0, (len - 1 - i) - 1);//len-1-i 代表这一趟的最后一个节点下标 这个节点这一趟处理结束后，就不再需要了
}
}
4.总结：堆排序属于排序中较难的一种，一定要对比图去理解。堆排序的时间复杂度是O(nlogn) 空间复杂度O(1) 稳定性：不稳定（存在跳跃交换）
