堆排序的分析及实现

（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。二叉堆可以分为两种形式：最大堆和最小堆。若将记录按从大到小排列，建“小”顶堆。若将记录按从小到大排，建“大”顶堆。说明：在堆排序算法中，我们使用的是最大堆，最小堆通常用于构造优先队列。算法分析：时间复杂度是O（nlogn）。堆排序属于原址排序：任何时候都只需要常数个额外的元素空间存储临时数据。堆排序是不稳定的排序算法。#include <stdio.h>
#define LEFT（i） 2 * i
#define RIGHT（i） 2 * i + 1void MaxHeapAjust（int A[], int i, int len） //调整节点i满足最大堆性质
{
int l = LEFT（i）;
int r = RIGHT（i）;
int largest, tmp; if （l <= len && A[l - 1] > A[i - 1]）
{
largest = l;
}
else
{
largest = i;
}
if （r <= len && A[r - 1] > A[largest - 1]）
{
largest = r;
} if （i ！= largest）
{
tmp = A[i - 1];
A[i - 1] = A[largest - 1];
A[largest - 1] = tmp; MaxHeapAjust（A, largest, len）;
}
}void BuildMaxHeap（int A[], int len） //构造最大堆
{
for （int i = len / 2; i > 0; i--）
{
MaxHeapAjust（A, i, len）;
}
}void HeapSort（int A[], int len） //堆排序
{
int tmp;
BuildMaxHeap（A, len）;
for （int i = len; i > 1; i--）
{
tmp = A[i - 1];
A[i - 1] = A[0];
A[0] = tmp; MaxHeapAjust（A, 1, i - 1）;
}
}int main（void）
{
int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
HeapSort（A, 10）;
for （int i = 0; i < 10; i++）
{
printf（"%d ", A[i]）;
}
printf（" "）; return 0;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-02/113463.htm