【概念】堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]]>=A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂?！酒鹪础?991年的計算機(jī)先驅(qū)獎獲得者、斯坦福大學(xué)計算機(jī)科學(xué)系教授羅伯特·弗洛伊德(RobertW．Floyd）和威廉姆斯(J．Williams）在1964年共同發(fā)明了著名的堆排序算法（HeapSort)?！竞喗椤慷雅判蚶昧舜蟾眩ɑ蛐「眩┒秧斢涗浀年P(guān)鍵字最大（或最?。┻@一特征，使得在當(dāng)前無序區(qū)中選取最大（或最?。╆P(guān)鍵字的記錄變得簡單。（1）用大根堆排序的基本思想①先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)②再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key③由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆?！钡綗o序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作：①建堆，建堆是不斷調(diào)整堆的過程，從len/2處開始調(diào)整，一直到第一個節(jié)點(diǎn)，此處len是堆中元素的個數(shù)。建堆的過程是線性的過程，從len/2到0處一直調(diào)用調(diào)整堆的過程，相當(dāng)于o(h1)+o(h2)…+o(hlen/2)其中h表示節(jié)點(diǎn)的深度，len/2表示節(jié)點(diǎn)的個數(shù)，這是一個求和的過程，結(jié)果是線性的O(n)。②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i)，選出三者最大(或者最小)者，如果最大（?。┲挡皇枪?jié)點(diǎn)i而是它的一個孩子節(jié)點(diǎn)，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過程，這是一個遞歸的過程。調(diào)整堆的過程時間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的。③堆排序：堆排序是利用上面的兩個過程來進(jìn)行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個節(jié)點(diǎn)進(jìn)行交換)，將前面len-1個節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程，然后再將根節(jié)點(diǎn)取出，這樣一直到所有節(jié)點(diǎn)都取出。堆排序過程的時間復(fù)雜度是O(nlgn)。因?yàn)榻ǘ训臅r間復(fù)雜度是O(n)（調(diào)用一次）；調(diào)整堆的時間復(fù)雜度是lgn，調(diào)用了n-1次，所以堆排序的時間復(fù)雜度是O(nlgn)[2]注意：①只需做n-1趟排序，選出較大的n-1個關(guān)鍵字即可以使得文件遞增有序。②用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個向量為止【特點(diǎn)】堆排序（HeapSort）是一樹形選擇排序。堆排序的特點(diǎn)是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系（參見二叉樹的順序存儲結(jié)構(gòu)），在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗洝舅惴ǚ治觥慷雅判虻臅r間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實(shí)現(xiàn)的。平均性能：O(N*logN)。其他性能：由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1）。它是不穩(wěn)定的排序方法。（排序的穩(wěn)定性是指如果在排序的序列中，存在前后相同的兩個元素的話，排序前和排序后他們的相對位置不發(fā)生變化）。

-x language filename
　 設(shè)定文檔所使用的語言,使后綴名無效,對以后的多個有效.也就是根據(jù)約定C語言的后綴名稱是.c的，而C++的后綴名是.C或.cpp,假如您很個性，決定您的C代碼文檔的后綴名是.pig 哈哈，那您就要用這個參數(shù),這個參數(shù)對他后面的文檔名都起作用，除非到了下一個參數(shù)的使用。
　　能夠使用的參數(shù)嗎有下面的這些
　　`c', `objective-c', `c-header', `c++', `cpp-output', `assembler', and `assembler-with-cpp'.
　　看到英文，應(yīng)該能夠理解的。
　　例子用法:
　　gcc -x c hello.pig