【概念】堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]]
公司主營業(yè)務(wù)：成都做網(wǎng)站、成都網(wǎng)站制作、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)公司是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)公司推出蟠龍免費(fèi)做網(wǎng)站回饋大家。
=
A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。
【起源】
1991年的計(jì)算機(jī)先驅(qū)獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德(Robert
W．Floyd）和威廉姆斯(J．Williams）在1964年共同發(fā)明了著名的堆排序算法（
Heap
Sort
)。
【簡介】
堆排序利用了大根堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最?。┻@一特征，使得在當(dāng)前無序區(qū)中選取最大（或最?。╆P(guān)鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
①
先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無序區(qū)
②
再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個(gè)記錄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ū)間的最后一個(gè)記錄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ū)只有一個(gè)元素為止。
（2）大根堆排序算法的基本操作：
①建堆，建堆是不斷調(diào)整堆的過程，從len/2處開始調(diào)整，一直到第一個(gè)節(jié)點(diǎn)，此處len是堆中元素的個(gè)數(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)的個(gè)數(shù)，這是一個(gè)求和的過程，結(jié)果是線性的O(n)。
②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會(huì)用到，而且在堆排序過程中也會(huì)用到。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i)，選出三者最大(或者最小)者，如果最大（?。┲挡皇枪?jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn)，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過程，這是一個(gè)遞歸的過程。調(diào)整堆的過程時(shí)間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的。
③堆排序：堆排序是利用上面的兩個(gè)過程來進(jìn)行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換)，將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程，然后再將根節(jié)點(diǎn)取出，這樣一直到所有節(jié)點(diǎn)都取出。堆排序過程的時(shí)間復(fù)雜度是O(nlgn)。因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是O(n)（調(diào)用一次）；調(diào)整堆的時(shí)間復(fù)雜度是lgn，調(diào)用了n-1次，所以堆排序的時(shí)間復(fù)雜度是O(nlgn)[2]
注意：
①只需做n-1趟排序，選出較大的n-1個(gè)關(guān)鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時(shí)刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止
【特點(diǎn)】
堆排序（HeapSort）是一樹形選擇排序。堆排序的特點(diǎn)是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系（參見二叉樹的順序存儲(chǔ)結(jié)構(gòu)），在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗?/p>
【算法分析】
堆排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開銷構(gòu)成，它們均是通過調(diào)用Heapify實(shí)現(xiàn)的。
平均性能：O(N*logN)。
其他性能：由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1）。它是不穩(wěn)定的排序方法。（排序的穩(wěn)定性是指如果在排序的序列中，存在前后相同的兩個(gè)元素的話，排序前
和排序后他們的相對(duì)位置不發(fā)生變化）。
堆排序就是將所有待排序的元素組成一個(gè)堆，然后不斷彈出堆頂?shù)脑夭⒄{(diào)用函數(shù)維持堆序，直到所有元素均被彈出后，排序完成。被彈出的元素序列即一個(gè)有序數(shù)列。 ?
一般做法是這樣：
當(dāng)一個(gè)節(jié)點(diǎn)被插入時(shí)，將該節(jié)點(diǎn)放在堆的末尾（這是為了保證堆是完全二叉樹）然后將該節(jié)點(diǎn)與它的父節(jié)點(diǎn)比較，看該節(jié)點(diǎn)是否大于（或小于）其父節(jié)點(diǎn)，即判斷當(dāng)前的堆是否滿足堆序。如果不滿足，則將該節(jié)點(diǎn)與其父節(jié)點(diǎn)交換。
再將該節(jié)點(diǎn)與其新的父節(jié)點(diǎn)做比較，依此類推，直到該節(jié)點(diǎn)不再需要與其父節(jié)點(diǎn)交換為止。（即滿足堆序時(shí)停止） ?當(dāng)一個(gè)根節(jié)點(diǎn)被彈出（即被從堆中刪除）時(shí)，將堆最尾部的節(jié)點(diǎn)移動(dòng)到頭結(jié)點(diǎn)的位置，然后將該節(jié)點(diǎn)不斷與其子節(jié)點(diǎn)比較，如果不符合堆序則交換，直到符合堆序?yàn)橹埂?/p>
擴(kuò)展資料：
堆的操作
堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
在堆的數(shù)據(jù)結(jié)構(gòu)中，堆中的最大值總是位于根節(jié)點(diǎn)（在優(yōu)先隊(duì)列中使用堆的話堆中的最小值位于根節(jié)點(diǎn)）。堆中定義以下幾種操作：
最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序
堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
參考資料：
百度百科-堆排序
#includestdio.h
#includestdlib.h
void BubbleSort(int a[], const int first, const int last);//冒泡排序
void InsertSort(int a[], const int first, const int last);//插入排序
void SelectSort(int a[], const int first, const int last);//選擇排序
void MergeSort(int a[], const int p, const int r);//合并排序
void QuickSort(int a[],const int p,const int r);//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t);//希爾排序
void HeapSort(int a[],const int p, int r); //堆排序
void StoogeSort(int a[],const int p,const int r);//Stooge排序(不用)算法復(fù)雜度沒算清楚
void main()
{
//插入排序算法
int a[11] = {6,4,5,3,2,1};
int dlta[]={9,5,3,2,1};
//BubbleSort(a,0,5);
//InsertSort(a,0,5);
//SelectSort(a,0,5);
//MergeSort(a,0,5);
//QuickSort(a,0,5);
//ShellSort(a,0,5,dlta,5);
HeapSort(a,0,5);
//StoogeSort(a,0,5);
for(int i=0; i=5;i++)
{
printf("%d ",a[i]);
}
}
/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//實(shí)現(xiàn)對(duì)數(shù)組a[]中a[first]到a[last]升序的“冒泡”排序
int i,j,temp;
for(i=first; i=last; i++)
{
for(j=first; j last-i; j++)
{
if(a[j] a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//實(shí)現(xiàn)對(duì)數(shù)組a[]中a[first]到a[last]升序的“插入”排序
//最壞情況為n的平方，，多用于小數(shù)組
int i,j,temp;
for(i=first+1; i=last; i++)
{
temp = a[i];
j = i - 1;
while((j = 0) (a[j] temp))
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
/************************選擇排序***********************/
void SelectSort(int a[], int first, int last)
{
//實(shí)現(xiàn)對(duì)數(shù)組a[]中a[first]到a[last]升序的“選擇”排序
int i, j, temp, num;
for(i=first; ilast; i++)
{
num = i;
for(j=i+1; j=last; j++)
{
if(a[j] a[num])
{
num = j;
}
}
if(i != num)
{
temp = a[num];
a[num] = a[i];
a[i] = temp;
}
}
}
/************************合并排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合并排序算法中的實(shí)現(xiàn)合并的子程序
int iLLength,iRLength;
int *L, *R, i, j, k;
iLLength = q - p + 1;
iRLength = r - q;
L = (int *)malloc(iLLength*sizeof(int)); //或者 C++中 new int[iLLength];
R = (int *)malloc(iRLength*sizeof(int)); //或者 C++中 new int[iRLength];
if(L == 0 || R== 0)
{
printf("內(nèi)存分配失敗?。?！");
return;
}
for(i=0; iiLLength; i++)
{
L[i] = a[p+i];
}
for(j=0; jiRLength; j++)
{
R[j] = a[q+j+1];
}
i = 0;
j = 0;
for(k=p; k=r; k++)
{
if((iiLLength) (jiRLength) (L[i]=R[j]) || (j == iRLength))
{
a[k] = L[i];
i++;
}
else if(jiRLength)
{
a[k] = R[j];
j++;
}
}
free(R);free(L);
}
void MergeSort(int a[],const int p,const int r)
{
//合并排序算法-主程序
//n*lg(n),系數(shù)較小
int q;
if(pr)
{
q = (p+r)/2;
MergeSort(a,p,q);
MergeSort(a,q+1,r);
Merge(a,p,q,r);
}
}
/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge算法
int temp, k;
if(a[p]a[r])
{
temp = a[p];
a[p] = a[r];
a[r] = temp;
}
if((p+1) = r)
{
return;
}
k = (r-p+1)/3;
StoogeSort(a,p,r-k);
StoogeSort(a,p+k,r);
StoogeSort(a,p,r-k);
}
/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(關(guān)鍵)分治過程
int temp, x, i, j;
x = a[r];
i = p - 1;
for(j=p; jr; j++)
{
if(a[j] = x)
{
i = i + 1;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序算法-主程序
//與下面的“尾遞歸實(shí)現(xiàn)方法”比較，缺點(diǎn)：右邊數(shù)組的遞歸不是必須的，增加了運(yùn)行堆棧深度和調(diào)用開銷
int q;
if(p r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序算法-主程序
//“尾遞歸實(shí)現(xiàn)方法”是對(duì)上面的快速排序主程序?qū)崿F(xiàn)的一種優(yōu)化
//系數(shù)較小,常用大數(shù)組
int q;
while(p r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
p = q + 1;
}
}
/************************希爾排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希爾排序算法的關(guān)鍵子程序-插入排序子程序
int i, j, temp;
for(i=p+dk; i=r; i++)
{
if(a[i] a[i-dk])
{
temp = a[i];
for(j=i-dk; ((j=0) (temp a[j])); j -= dk)
{
a[j+dk] = a[j];
}
a[j+dk] = temp;
}
}
}
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希爾排序算法-主程序
//按增量序列dlta[]中的前t個(gè)增量，實(shí)現(xiàn)對(duì)數(shù)組a[]中a[p]到a[r]的排序
//dlta[]可能取值如：1,2,3,5,9 dala[k]=2^(t-k+1)-1 其中0=k=t=ld(b-1)
//增量序列的最后一個(gè)值必須是1
//增量序列中的值沒有除1以外的因子， 其精確時(shí)間復(fù)雜度：數(shù)學(xué)上尚未解決的難題
int k;
for(k=0; kt; k++)
{
ShellInsert(a,p,r,dlta[k]);
}
}
/************************堆排序***********************/
//堆排序，不如快速排序
//但是可用其來實(shí)現(xiàn)“優(yōu)先級(jí)隊(duì)列”
int Parent(int i)
{
return ((i+1)/2-1);
}
int Right(int i)
{
return (2*(i+1)-1);
}
int Left(int i)
{
return (2*(i+1));
}
void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp;
l = Left(i);
r = Right(i);
largest = ((l=hplast) (a[l]a[i])) ? l:i;
if((r=hplast) (a[r]a[largest]))
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
Max_Heapify(a,hplast,largest);
}
}
void Build_Max_Heap(int a[],const int p, const int r)
{
int i;
for(i = (p+r)/2; i=p; i--)
{
Max_Heapify(a,r,i);
}
}
void HeapSort(int a[],const int p, int r)
{
int i,temp;
Build_Max_Heap(a,p,r);
for(i = r; i p; i--)
{
temp = a[p];
a[p] = a[i];
a[i] = temp;
r -= 1;
Max_Heapify(a,r,0);
}
}
重慶分公司
重慶分公司
