算法表述：
堆排序的基本原理為將待排序序列構(gòu)造成一個(gè)大根堆，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)大根堆，重復(fù)上述操作，最終序列為有序。
備注：大根堆是每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值；小根堆是每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值。
如圖所示：
而實(shí)際上堆的存儲(chǔ)形式是一維數(shù)組。
算法執(zhí)行過(guò)程分析：
例如:25、15、88、45、8、1、33、21、55、6
如圖所示：
具體步驟:
說(shuō)明：最開始 i 為最后一個(gè)結(jié)點(diǎn)的位置，依據(jù)樹的性質(zhì)，推算該結(jié)點(diǎn)的雙親結(jié)點(diǎn)，我們將之標(biāo)記為 s。接下來(lái)比較雙親結(jié)點(diǎn)和葉子結(jié)點(diǎn)，并進(jìn)行交換，然后找到下一個(gè)雙親結(jié)點(diǎn)，重復(fù)上述操作算法分析中實(shí)現(xiàn)堆排序c語(yǔ)言程序，直到最后達(dá)到根節(jié)點(diǎn)，比較交換完成后，此時(shí)大根堆或小根堆便建立完成。（下面我們按照從小到大進(jìn)行排序，因此我們建立大根堆）
(1)第一次排序:
(2)第二次排序:
以此類推,可得最后一次排序情況為:
此時(shí)排為大根堆,接下來(lái)只需要將根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換值,然后對(duì)根節(jié)點(diǎn)進(jìn)行一次排序即可.
如圖所示:此時(shí)排為大根堆,接下來(lái)只需要將根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換值,然后對(duì)根節(jié)點(diǎn)進(jìn)行一次排序即可.
如圖所示:
代碼實(shí)現(xiàn):
void Adjust (int *arr,int start,int end)
{
int temp = arr[start];
for(int i = 2*start +1;i<= end;i = 2*i+1) //i是左孩子下標(biāo)
{
//判斷是否有右孩子
if(i < end && arr[i] < arr[i+1]) //說(shuō)明有右孩子,左孩子小于右孩子
{
i++;
}
if(arr[i] > temp)
{
arr[start] = arr[i];
start = i;
}
else
{
break;
}
}
arr[start] = temp;
}
void Heap_Sort(int *arr,int len)
{
int i = 0;
for(i = (len-1-1)/2;i >= 0;i--)
{
Adjust(arr,i,len-1);
}
//此時(shí)已經(jīng)是大根堆
for(i = 0;i < len-1;i++)
{
int temp = arr[0];
arr[0] = arr[len-1-i];
arr[len-1-i] = temp;
Adjust(arr,0,len-1-i-1);
}
}備注:
父====>>子
若父為n，則其右孩子為2n+1；左孩子為2n+2。
子====>>父
若子為n算法分析中實(shí)現(xiàn)堆排序c語(yǔ)言程序，則其父為(n-1)/2;
總結(jié):