堆排序
堆排序简单的来说就是一种选择排序的优化.
1.堆
堆实际上是一颗完全二叉树,完全二叉树,所有父节点有两个儿子，或者最后一个父节点只有左儿子.并且父节点的关键字大于或等于所有子节点的关键字
完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
堆表面看也就是逻辑结构是一个树型,然而实际上在内存中是以数组的结构线性存储.
堆分为大顶堆和小顶堆.
大顶堆:根节点的关键字最大.
小顶堆:根节点的关键字最小 .
大顶堆如下 (根节点最小~)
2.堆排序思想
要使用堆排序,首先我们要建立以个大顶堆~，如上图所示
建堆过程:
假设有n个节点，从最后一个父节点(标号为5)起,首先比较最后一个父节点（上图中标号为5）的所有子节点的大小得出较大的子节点,然后用较大的子节点和父节点比较,若大于父节点则交换。
接着到倒数第二个父节点(上图编号为4)，比较所有子节点的大小得出较大的子节点，然后用较大的子节点和父节点比较，若大于父节点则交换。
....
于此类推，
直到最后一次父节点为根节点时（上图编号为1），此时根节点是所有节点的最大值，得到大顶堆，且每一个父节点的关键字大于所有子节点。
小顶堆则最小值放到根节点。
现在开始排序～
比如我们利用大顶堆建堆能得到所有节点中最大的节点，在根部，然后我们用根节点的元素（最大）与最后一个节点交换，最后一个节点则用来存放此刻堆的最大值，现在我们假设最后一个节点被排除了，这样就出现了一个新的“ 堆 ”且节点个数为n-1，这个堆不满足大顶堆的性质，所以再来一次建新堆的过程，这时根结点又一次为最大值（当然前提是我们已经假设先前的最大节点被排除掉了，此时的最大节点为先前次大），用根节点和新堆的最后一个元素交换，最后一个元素用来存放新堆的最大值。
重复此过程。
我们用不断的建立大顶堆（新堆元素每次减 1），来获得每次新堆的最大值，所以能得到排序后的结果～
建立大顶堆排序，排序结果为从小到大
建立小顶堆排序，排序结果为从大到小
3.代码如下
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int Capacity;
int *array;
};
//交换函数
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//建堆函数
void Adjustheap(struct Node *a)
{
int i;
i = a->Capacity / 2;
if(a->Capacity %2 == 1) //元素个数为奇数个和偶数个关系到最后一个父节点的儿子个数
{
while(i != 0)
{
if(a->array[2*i] < a->array[2*i+1]) //比较左右节点，我默认为左节点为较大节点
exchange(a->array+2*i, a->array+2*i+1);
if(a->array[i] < a->array[2*i]) //左节点和父节点比较,交换结果父节点为最大值
exchange(a->array+i, a->array+2*i);
i--;
}
}
else if(a->Capacity %2 == 0) //元素个数为偶数个情况
{
if(a->array[2*i] < a->array[i]) //因为最后一个父节点只有左子节点，情况特殊，单独处理
{
exchange(a->array+2*i, a->array+i);
}
i--;
while(i != 0)
{
if(a->array[2*i] < a->array[2*i+1])
exchange(a->array+2*i, a->array+2*i+1);
if(a->array[i] < a->array[2*i])
exchange(a->array+i, a->array+2*i);
i--;
}
}
exchange(a->array+1, a->array+(a->Capacity)); //根节点编号为1是最大值,与最后一个节点交换
a->Capacity--; //每次新堆的元素个数减1
}
int main()
{
struct Node *a;
int i;
int j;
printf("Capacity:");
scanf("%d",&a->Capacity);
j = a->Capacity;
a->array = (int *)malloc(sizeof(int) * (a->Capacity+1));
for(i = 1; i <= a->Capacity; i++)
{
scanf("%d",a->array+i);
}
while(a->Capacity >= 1)
{
Adjustheap(a);
}
for(i = 1; i <= j; i++)
{
printf("the value is %d\n",a->array[i]);
}
return 0;
}
运行结果如图：
a->array[1] 是每次找到的最大数。
今天看了看代码，当没有右节点我们也可以自己构造一个，根据排序的顺序可以给里面填充一个无穷大或无穷小的数字来解决。