2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(5)

　　堆排序

　　算法思想：堆排序(Heap Sort)是指利用堆(heaps)這種數(shù)據(jù)結(jié)構(gòu)來構(gòu)造的一種排序算法。

　　堆是一個(gè)近似完全二叉樹結(jié)構(gòu)，并同時(shí)滿足堆屬性：即子節(jié)點(diǎn)的鍵值或索引總是

　　小于(或者大于)它的父節(jié)點(diǎn)。

　　時(shí)間復(fù)雜度 o(nlogn)

　　空間復(fù)雜度 o(1)

　　比較次數(shù)：較多

　　*/

　　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]); //彈出最大值，重新對(duì)i-1個(gè)元素建堆

　　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;

　　}

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)