2011年软考程序员考试复习笔试知识点整理(5)9

　堆排序

　　算法思想：堆排序(Heap Sort)是指利用堆(heaps)这种数据结构来构造的一种排序算法。

　　堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是

　　小于(或者大于)它的父节点。

　　时间复杂度 o(nlogn)

　　空间复杂度 o(1)

　　比较次数：较多

　　*/

　　void heap_adjust(int array[],int i,int len)

　　{

　　int rc = array[i];

　　for(int j = 2 * i; j

　　{

　　if(j < len && array[j]< array[j+1]) j++;

　　if(rc >= array[j]) break;

　　array[i] = array[j]; i = j;

　　}

　　array[i] = rc;

　　}

　　void heap_sort(int array[],int len)

　　{

　　int i;

　　for(i = (len-1)/2; i >= 0; i--)

　　heap_adjust(array,i,len);

　　for( i = (len-1); i > 0; i--)

　　{

　　swap(array[0],array[i]); //弹出最大值，重新对i-1个元素建堆

　　heap_adjust(array,0,i-1);

　　}

　　}

　　int main()

　　{

　　int array[] = {45, 56, 76, 234, 1, 34,23, 2, 3, 55, 88, 100};

　　int len = sizeof(array)/sizeof(int);

　　//bubble_sort(array,len); //冒泡排序

　　/*insert_sort(array,len);*/ //插入排序

　　/*bi_insert_sort(array,len);*/ //二路插入排序

　　/*shell_sort(array,len);*/ //希尔排序

　　/*quick_sort(array,0,len-1);*/ //快速排序

　　/*select_sort(array,len);*/ //选择排序

　　/*merge_sort(array,0,len-1);*/ //归并排序

　　heap_sort(array,len); //堆排序

　　display(array,len);

　　return 0;

　　}