排序--堆排序【图文详解】
二叉树的相关概念
-
叶子：没有子节点的节点叫叶子节点
-
大根堆：所有的父亲大于儿子
-
小根堆：所有的儿子大于父亲
-
父亲于儿子的的下标关系：
父亲的下标为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];//把左右孩子的最大值给strat
start = i;//start赋值为i
}
else
{
break;//如果越界，跳出循环
}
}
arr[start] = tmp;//最后把原来start的值给补上
}
void HeapSort(int* arr, int len)//堆排序,O(nlogn),O(1),不稳定
{
int i;//数组下标
//第一次建立大根堆,从后往前,多次调整
//子是i，父是（子-1）/2
for (i = (len - 1 - 1) / 2; i >= 0; i--)//O（n）数学证明
//这个i是倒数第二层根的下标，比如说有11个数字，那么要从4下标开始调整
{
HeapAdjust(arr, i, len - 1);//第一次建立大根堆
//这里的len-1，不影响调整，放大了不影响
}
//每次将0下标的数字和待排序的最后一个交换,然后再次调整 堆调整的时间复杂度是logn
int 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)
稳定性：不稳定
本篇完！🍗
原文地址：https://blog.csdn.net/m0_75266675/article/details/142578863
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！