堆排序（大根堆）

堆的定义如下，n个关键字序列[1...n]称为堆，当且仅当满足：
a(i)>=a(2i)且a(i)>=a(2i+1)  这个为大根堆
a(i)<=a(2i)且a(i)<=a(2i + 1)  这个为小根堆

通过建堆得到大根堆
大根堆 87,45,78,32,17,65,53,9 可以看成
                    87
            45                78
        32        17        65        53
    9
    也就相当于是完全二叉树

#include<stdio.h>
void headadjust(int a[], int k, int i);
void swap(int *i, int *j)//交换堆顶和堆底元素
{int temp = *i;*i = *j; *j = temp;
}
void buildmaxheap(int a[], int len)//建立大根堆
{int i = 0;for (i = len / 2; i > 0; i--)//从i=[n/2]~1,反复调整堆headadjust(a, i, len);
}
void headadjust(int a[], int k, int len)//调整堆
{int i = 0;a[0] = a[k];//相当与根节点的复制值for (i = k * 2; i <=len; i *= 2)//从i较大的子节点向下筛选{if (i < len && a[i] < a[i + 1])//左孩子跟右孩子的大小i++;if (a[0] >= a[i])//根结点的值大于左右孩子直接退出break;else{a[k] = a[i];//否则交换孩子与根节点的值k = i;}}a[k] = a[0];//被筛选的值放在最后位置
}
int main()//堆排序
{int i = 0;int a[] = {0,53,17,78,9,45,65,87,32};int sz = sizeof(a) / sizeof(a[0]);printf("原来的数组为\n");for (i = 1; i < sz; i++)printf("%d ", a[i]);buildmaxheap(a, sz-1);//初始建堆for (i = sz-1; i > 1; i--){swap(&a[i], &a[1]);//调用swap()函数交换堆顶和堆底元素，此时堆得性质被破坏headadjust(a, 1, i - 1);//把剩余的i-1个元素整理成堆}printf("\n排完序的数组为\n");for (i = 1; i < sz; i++)printf("%d ", a[i]);return 0;
}