堆排序

介绍堆排序之前，先介绍一下堆。堆分为大根堆和小根堆，大根堆是指父节点的数据大于等于子节点的数据，小根堆是指父节点的数据小于等于子节点的数据。

堆排序就是指先把数据写成堆(大根堆或小根堆)的形式，然后输出堆顶元素，接着进行堆调整，是剩下的n-1个元素重新构成堆。如此反复执行，就可以得到有序数列。以大根堆为例，就把大的数放到后面， 因此，大根堆适用于升序，小根堆适用于降序。

那么这里就有两个问题：

1、初始的数据都是无序的，如何写成堆的形式？

2、输出堆顶元素后，如何进行调整？

针对第一个问题，由无序到堆的形式也就是堆调整，所以先说堆调整的过程。以下面一组数据为例:-1 1 5 6 3 4 2 8 6 1，堆排序时第一个数不参与排序，下标从1开始写成堆形式。

首先找到有子节点的结点，从其中下标最大的开始，依次往上进行调整。从根节点开始也可以但是调整次数多，所以从后边开始。在示例中，从4开始，取其子节点中最大的结点8与父节点4比较，如果子节点大于父节点进行交换。然后是结点3，依次往上。

要注意一点，结点1和结点2交换后，还要与结点3、4进行比较，直到所有都满足大根堆，这里也就解决了第一个问题。

然后，输出堆顶元素。把堆顶元素和最后一个无序的元素交换（下图中红色方框里的也可以看成已经有序的部分），剩下的进行堆调整。

如果设子节点下标为j，则其对应的父节点为i=j/2；

如果设父节点下表为i，则对应的左结点为j=2*i，右节点为j=2*i+1。

代码如下：

//堆调整
void HeapAdjust(int arr[],int i,int len)
//i为父节点，len为有效的数据长度，即不包括arr[0]
{
int j;//左子树
for(j=2*i;j<=len;j=2*j)
{
if(j<len && arr[j+1]>arr[j])//找出左子树和右子树中最大的值,j<len 左右子树都有
{
j++;
}
if(arr[j]<arr[i])
break;
arr[0] = arr[i];
arr[i] = arr[j];
arr[j] = arr[0];
i=j;
}
}

//堆排序
void HeapSort(int arr[],int len)
{
int tmp;
for(int i=len/2;i>0;--i)//将无序的数据写成大根堆形式
{
HeapAdjust(arr,i,len);
}
for(int j=len;j>0;--j)
{
tmp = arr[1];
arr[1] = arr[j];
arr[j] = tmp;
HeapAdjust(arr,1,len);//交换之后，从根节点开始调整
}
}