堆排序之我见

堆排序像合并排序而不像插入排序，堆排序的运行时间为O(nlgn)。像插入排序而不像合并排序，它是一种原地排序算法：在任何时候，数组中只有常数个元素存储在输入数组之外。这样，堆排序就把这两种算法的优点结合起来。

我以百度笔试题来解释堆排序。

堆数据结构是一种数组对象，它可以被视为一颗完全二叉树。树中的每个结点与数组中存放该值的那个元素对应。树的每一层都是填满的，最后一层可能除外。

在堆排序算法中，我们使用最大堆。最小堆通常在构造优先队列时使用。

有个结论：子数组A[n/2+1.....n]中的元素都是树中的叶子，因此每个都可看作是只含一个元素的堆。

#include<stdio.h>#define N 1002void swap(int *a,int *b){/*if(*a != *b){*a ^= *b;*b ^= *a;*a ^= *b;}*/*a = *a + *b;*b = *a - *b;*a = *a - *b;}void print(int *a,int n){int i;for(i=1;i<n;i++)printf("%4d",a[i]);printf("\n");}void max_heapadjust(int *a,int i,int size){int l = 2*i;          //i的左孩子结点序号int r = 2*i + 1;      //i的右孩子结点序号int max = i;if(l<=size && a[l]>a[i])max = l;if(r<=size && a[r]>a[max])max = r;if(max != i){swap(&a[i],&a[max]);max_heapadjust(a,max,size);   //交换后a[max]可能违反最大堆的性质，因此要递归调整。}}void build_max_heap(int *a,int size){int i;for(i=size/2;i>=1;i--)              //非叶结点最大序号为size/2。max_heapadjust(a,i,size);}void heapsort(int *a,int size){build_max_heap(a,size);int i;for(i=size;i>=2;i--){swap(&a[1],&a[i]);          //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面。max_heapadjust(a,1,i-1);    //重新调整堆顶结点使其成为最大堆。}}int main(int argc,char *argv[]){int a[N];int i;for(i=1;i<N;i++)a[i] = N-i;print(a,N);heapsort(a,N-1);print(a,N);return 0;}