選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法（比如序列[5， 5， 3]第一次就將第一個[5]與[3]交換，導(dǎo)致第一個5挪動到第二個5后面）。

基本選擇排序

n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：
①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。
②第1趟排序
在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。
……
③第i趟排序
第i趟排序開始時，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。

堆排序

堆排序利用了大根堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最小）這一特征，使得在當(dāng)前無序區(qū)中選取最大（或最小）關(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)整為堆。
……
直到無序區(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)鍵字最大（或最?。┑挠涗?/p>