堆排序

堆：heap 一種數(shù)據(jù)結(jié)構(gòu) 完全二叉樹（每個父節(jié)點(diǎn)最多只有兩個子節(jié)點(diǎn)左節(jié)點(diǎn)和右結(jié)點(diǎn)） 常用來做堆排序和二叉樹排序 每一個堆都可以用數(shù)組來表示 節(jié)點(diǎn)與數(shù)組下表對應(yīng)關(guān)系為：

堆頂位置為數(shù)組第一個下標(biāo)? ? 給定一個數(shù)組下標(biāo)i? 父節(jié)點(diǎn)i =i/2； 左子節(jié)點(diǎn) = i*2 右子節(jié)點(diǎn)= 2i+1；

二叉堆一般分為 最大堆 和 最小堆 最大堆是每一個父節(jié)點(diǎn)都大于它的子節(jié)點(diǎn) 最小堆與之相反

一個堆與數(shù)組的對應(yīng)關(guān)系

?堆排序的步驟：

1、先把一個數(shù)組表示為一個堆，并且對這個堆進(jìn)行最大堆排序

2、將排完序的堆頂元素與最后一個元素交換位置并且對交換位置后的堆再次進(jìn)行堆排序（將倒數(shù)第二個元素不斷與堆頂元素進(jìn)行比較構(gòu)造成最大堆），最后一個元素已經(jīng)排完序 在對前面的元素進(jìn)行排序 每次出來一個這次排序最大的元素?

堆排序的C語言版

堆排序第二步

堆排序效率：時間復(fù)雜度為（nlogn） 空間復(fù)雜度（O（1）） 該排序為不穩(wěn)定的排序。