算法思想：

建立一个大根堆;（将一棵普通的树转化为大根堆）
每次将根和待排序的最后一个交换,然后再调整,循环len-1次即可;

调整为大根堆的方法：

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

堆调整的代码实现：

void  HeapAdjust(int* arr, int start, int end)//堆调整
{int  tmp = arr[start];for (int i = 2 * start + 1; i <= end; i=2*i+1){if (i < end && arr[i] < arr[i + 1])//如果有右孩子,并且左孩子的值小于右孩子{i++;}//i一定是左右孩子的最大值if (arr[i] > tmp){arr[start] = arr[i];start = i;}else{break;}}arr[start] = tmp;
}

代码实现：

void   HeapSort(int* arr, int len)//堆排序,O(nlogn),O(1),不稳定
{int i;//第一次建立大根堆,从后往前,多次调整for (i = (len - 1 - 1) / 2; i >= 0; i--)//有一个数学证明,O(n){HeapAdjust(arr, i, len - 1);//第一次建立大根堆}//每次将根和待排序的最后一个交换,然后再次调整int  tmp;for (i = 0; i < len - 1; i++)  //O(nlogn){//交换tmp = arr[0];arr[0] = arr[len - 1 - i];arr[len - 1 - i] = tmp;//再次调整HeapAdjust(arr, 0, len -1-i  -1);//堆调整}
}

效率分析：

时间复杂度:O(nlogn),系数大,空间复杂度O(1),不稳定