堆排序
堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlog2n)。
堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。
基本思想
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。
大根堆和小根堆
堆：是一颗完全二叉树。
大根堆：所有节点的子节点比其自身小的堆
小根堆：所有节点的子节点比其自身大的堆
完全二叉树的基本性质
数组中有n个元素，i是节点
1 <= i <= n/2 就是说数组的后一半元素都是叶子节点。
i的父节点位置：i/2
i左子节点位置：i*2
i右子节点位置：i*2 + 1
如一个数组
物理结构：15 20 35 25 30 40 50
逻辑结构：
15
/
20 35
/ /
25 30 40 50
这是一个小根堆，所有节点的子节点比其自身大。15，20，35是节点，其它的都是叶子。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
（以上文字引用自该博文：http://www.cnblogs.com/kidfruit/archive/2010/03/23/1692837.html，感谢作者）
由于博主的程序是用C#写的，而这里是C语言栏，所以改写为C的格式，供读者参考：
#include <stdio.h>
void heap_sort (int *a, int len);
void heap_build (int *a, int len);
void heap_adjust (int *a, int len, int loc);
void print (int *a, int len);
inline static void swap (int *a, int *b);
int main ()
{
int a[] = { 40, 10, 20, 15, 35, 0, 16, 4, 14, 7, 9, 3, 8, 1 };
heap_sort (a, sizeof (a) / sizeof (a[0]));
print (a, sizeof (a) / sizeof (a[0]));
return 0;
}
void print (int *a, int len)
{
int i = 0;
for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");
}
inline static void swap (int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
void heap_sort (int *a, int len)
{
int i = 0;
heap_build (a, len);
for (i=len-1; i > 0; i--)
{
swap (a+i, a);
heap_adjust (a, i, 0);
}
}
void heap_build (int *a, int len)
{
int i = 0;
for (i=len/2-1; i != 0; i--)
{
heap_adjust (a, len, i);
}
}
void heap_adjust (int *a, int len, int loc)
{
int t = 0;
if (loc < len/2 && (a[loc] < a[2*loc] || a[loc] < a[2*loc+1]))
{
t = a[loc] < a[2*loc] ? 2*loc: 2*loc + 1;
swap (a+loc, a+t);
heap_adjust (a, len, t);
}
}