預(yù)備知識

堆排序

　　堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。首先簡單了解下堆結(jié)構(gòu)。

堆

　　堆是具有以下性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆；或者每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆。如下圖：

萬碼學(xué)堂,電腦培訓(xùn),計算機(jī)培訓(xùn),Java培訓(xùn),JavaEE開發(fā)培訓(xùn),青島軟件培訓(xùn),軟件工程師培訓(xùn)

同時，我們對堆中的結(jié)點(diǎn)按層進(jìn)行編號，將這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個樣子

網(wǎng)友評論