排序--堆排序【图文详解】
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是要交换的数字，交换完的数字不需要再参加调整
}
}