排序--堆排序【图文详解】
二叉树的相关概念
-
叶子：没有子节点的节点叫叶子节点
-
大根堆：所有的父亲大于儿子
-
小根堆：所有的儿子大于父亲
-
父亲于儿子的的下标关系：
父亲的下标为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是要交换的数字，交换完的数字不需要再参加调整 }
}建立大根堆的时间复杂度：O(n) 堆调整的时间复杂度是O(logn)
时间复杂度：O(nlogn)
空间复杂度：O（1)
稳定性：不稳定
本篇完！🍗