堆排序是利用構(gòu)建“堆”的方法確定具有最大值的數(shù)據(jù)元素，并把該元素與最后位置上的元素交換。可將任意一個(gè)由n個(gè)數(shù)據(jù)元素構(gòu)成的序列按照（a1，a2，...，an），按照從左到右的順序按層排列構(gòu)成一棵與該序列對(duì)應(yīng)的完全二叉樹(shù)。

一棵完全二叉樹(shù)是一個(gè)堆，當(dāng)且僅當(dāng)完全二叉樹(shù)的每棵子樹(shù)的根值ai≥其左子樹(shù)的根值a2i，同時(shí)ai≥其右子樹(shù)的根值a 2i+1 (1<i<n/2)。

實(shí)現(xiàn)堆排序需要實(shí)現(xiàn)兩個(gè)問(wèn)題：
如何由無(wú)序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？

思路：

堆排序算法思想：
1、從最后一個(gè)非葉子節(jié)點(diǎn)逐步到樹(shù)根，對(duì)每個(gè)子樹(shù)進(jìn)行調(diào)整堆。

2、重復(fù)n-1次如下處理：將堆的根與最后一個(gè)葉子交換，除最后一個(gè)葉子之外剩余部分再調(diào)整為堆。
調(diào)整堆算法思想：
1、將樹(shù)根與其左右子樹(shù)根值最大者交換；（大頂堆）

2、對(duì)交換后的左（或右）子樹(shù)重復(fù)過(guò)程1，直到左（或右）子樹(shù)為堆。

時(shí)間復(fù)雜度：O(nlogn)

代碼：

調(diào)整堆算法：

void HeapAdjust(int *array,int i,int length){	//調(diào)整堆 
	int leftChild=2*i+1;		//定義左右孩子 
	int rightChild=2*i+2;
	int max=i;		//初始化，假設(shè)左右孩子的雙親節(jié)點(diǎn)就是最大值 
	if(leftChild<length&&array[leftChild]>array[max]){
		max=leftChild;
	}
	if(rightChild<length&&array[rightChild]>array[max]){
		max=rightChild;
	}
	if(max!=i){		//若最大值不是雙親節(jié)點(diǎn)，則交換值 
		swap(array[max],array[i]);
		HeapAdjust(array,max,length);	//遞歸，使其子樹(shù)也為堆 
	}
}

堆排序算法：

void HeapSort(int *array,int length){	//堆排序 
	for(int i=length/2-1;i>=0;i--){		//從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向上遍歷，建立堆 
		HeapAdjust(array,i,length);
	}
	for(int j=length-1;j>0;j--){		//調(diào)整堆 ，此處不需要j=0  
		swap(array[0],array[j]);
		HeapAdjust(array,0,j);		//因?yàn)槊拷粨Q一次之后，就把最大值拿出(不再參與調(diào)整堆)，第三個(gè)參數(shù)應(yīng)該寫j而不是length 
		Print(array,length); 
	}
}

完整代碼：

//堆排序
#include <iostream> 
using namespace std;
void Print(int array[],int length){	//每執(zhí)行一次打印一次序列 
	for(int i=0;i<length;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
}
void HeapAdjust(int *array,int i,int length){	//調(diào)整堆 
	int leftChild=2*i+1;		//定義左右孩子 
	int rightChild=2*i+2;
	int max=i;		//初始化，假設(shè)左右孩子的雙親節(jié)點(diǎn)就是最大值 
	if(leftChild<length&&array[leftChild]>array[max]){
		max=leftChild;
	}
	if(rightChild<length&&array[rightChild]>array[max]){
		max=rightChild;
	}
	if(max!=i){		//若最大值不是雙親節(jié)點(diǎn)，則交換值 
		swap(array[max],array[i]);
		HeapAdjust(array,max,length);	//遞歸，使其子樹(shù)也為堆 
	}
}
void HeapSort(int *array,int length){	//堆排序 
	for(int i=length/2-1;i>=0;i--){		//從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向上遍歷，建立堆 
		HeapAdjust(array,i,length);
	}
	for(int j=length-1;j>0;j--){		//調(diào)整堆 ，此處不需要j=0  
		swap(array[0],array[j]);
		HeapAdjust(array,0,j);		//因?yàn)槊拷粨Q一次之后，就把最大值拿出(不再參與調(diào)整堆)，第三個(gè)參數(shù)應(yīng)該寫j而不是length 
		Print(array,length); 
	}
}
int main(){
	int array[]={49,38,65,97,76,13,27,49};
	int length=sizeof(array)/sizeof(*array);
	Print(array,length);			//先打印原始序列 
	HeapSort(array,length);
	return 0;
}

運(yùn)行示例：

第一行是原始序列，第二到八行分別是經(jīng)過(guò)7次調(diào)整堆所得到的序列。