排序--堆排序【图文详解】

二叉树的相关概念

叶子：没有子节点的节点叫叶子节点
大根堆：所有的父亲大于儿子
小根堆：所有的儿子大于父亲
父亲于儿子的的下标关系：

父亲的下标为i ，那么左孩子的下标为2*i+1，右孩子的下标为2i+2

子的下标是i ，父的下标为（i-1）/2

构建大根堆的方法

从最后一棵子树开始,从后往前调整;
每次调整,从上往下; 调整为大根堆;

图解

在这里插入图片描述

完整代码

void  HeapAdjust(int* arr, int start, int end)//堆调整，从倒数第二层开始调整
{int  tmp = arr[start];//先把start的值保存下来，要不然丢失数据//先找左孩子，2*strat+1，for (int i = 2 * start + 1; i <= end; i = 2 * i + 1){//把i定位为左右孩子的最大值下标if (i < end && arr[i] < arr[i + 1])//有右孩子,并且左孩子的值小于右孩子{i++;}//i一定是左右孩子的最大值//找到左右孩子的最大值后if (arr[i] > tmp){arr[start] = arr[i];//把左右孩子的最大值给stratstart = i;//start赋值为i}else{break;//如果越界，跳出循环}}arr[start] = tmp;//最后把原来start的值给补上
}void   HeapSort(int* arr, int len)//堆排序,O(nlogn),O(1),不稳定
{int i;//数组下标//第一次建立大根堆,从后往前,多次调整   //子是i，父是（子-1）/2for (i = (len - 1 - 1) / 2; i >= 0; i--)//O（n）数学证明//这个i是倒数第二层根的下标，比如说有11个数字，那么要从4下标开始调整{HeapAdjust(arr, i, len - 1);//第一次建立大根堆//这里的len-1，不影响调整，放大了不影响}//每次将0下标的数字和待排序的最后一个交换,然后再次调整  堆调整的时间复杂度是lognint  tmp;//临时变量for (i = 0; i < len - 1; i++)  //O(nlogn)  11个数字交换10次    {//交换    tmp = arr[0];    arr[0] = arr[len - 1 - i];//len-1-i是因为调整好了的数字不要再动了    arr[len - 1 - i] = tmp;    //再次调整    HeapAdjust(arr, 0, len - 1 - i - 1);//堆调整    //len-1-i-1的解释：len-1-i是要交换的数字，交换完的数字不需要再参加调整    }
}