算法表述：
堆排序的基本原理为将待排序序列构造成一个大根堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个大根堆，重复上述操作，最终序列为有序。
备注：大根堆是每个结点的值都大于或等于其左右孩子结点的值；小根堆是每个结点的值都小于或等于其左右孩子结点的值。
如图所示：
而实际上堆的存储形式是一维数组。
算法执行过程分析：
例如:25、15、88、45、8、1、33、21、55、6 如图所示：
具体步骤: 说明：最开始 i 为最后一个结点的位置，依据树的性质，推算该结点的双亲结点，我们将之标记为 s。接下来比较双亲结点和叶子结点，并进行交换，然后找到下一个双亲结点，重复上述操作，直到最后达到根节点，比较交换完成后，此时大根堆或小根堆便建立完成。（下面我们按照从小到大进行排序，因此我们建立大根堆） (1)第一次排序:
(2)第二次排序:
以此类推,可得最后一次排序情况为:
此时排为大根堆,接下来只需要将根节点和最后一个节点交换值,然后对根节点进行一次排序即可. 如图所示:此时排为大根堆,接下来只需要将根节点和最后一个节点交换值,然后对根节点进行一次排序即可. 如图所示:
代码实现:
void Adjust (int *arr,int start,int end)
{
int temp = arr[start];
for(int i = 2*start +1;i<= end;i = 2*i+1) //i是左孩子下标
{
//判断是否有右孩子
if(i < end && arr[i] < arr[i+1]) //说明有右孩子,左孩子小于右孩子
{
i++;
}
if(arr[i] > temp)
{
arr[start] = arr[i];
start = i;
}
else
{
break;
}
}
arr[start] = temp;
}
void Heap_Sort(int *arr,int len)
{
int i = 0;
for(i = (len-1-1)/2;i >= 0;i--)
{
Adjust(arr,i,len-1);
}
//此时已经是大根堆
for(i = 0;i < len-1;i++)
{
int temp = arr[0];
arr[0] = arr[len-1-i];
arr[len-1-i] = temp;
Adjust(arr,0,len-1-i-1);
}
}
备注:父====>>子 若父为n，则其右孩子为2n+1；左孩子为2n+2。 子====>>父 若子为n，则其父为(n-1)/2;
总结:
时间复杂度：O(nlog2n)空间复杂度：O(log2n)稳定性：不稳定排序
