堆排序算法实现
堆用数组来实现,但是其中元素有顺序,满足最大(小)堆的性质,如a[i]>a[i+1]&&a[i]>a[i+2],堆排序的思想是对于一个无序的数组,首先建堆,然后将第一个元素与最后一个元素交换位置,这样因为第一个元素是最大(小)值,就可以取出来了,再对其余N-1个元素进行堆得整理,代价为logn,然后再次取出第一个元素,以此类推,总的排序代价为O(N*logN)。注意建堆的代价为O(N)。
C++的实现代码如下:
/*建堆函数*/void buileHeap(int *a, int size){ int i; for(i=size/2;i>0;i--) //非叶节点的序号最大为size/2,注意节点序号从1开始,这样方便。 { heapAdjust(a, i, size); }}