說到堆排序，它的思想來源于優(yōu)先隊(duì)列，我們首先來說一下什么是優(yōu)先隊(duì)列。

一、優(yōu)先隊(duì)列

1.優(yōu)先隊(duì)列的定義：優(yōu)先隊(duì)列是允許以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：Insert（插入）相當(dāng)于入隊(duì)、DeleteMin（刪除最小元）。

2.使用數(shù)據(jù)結(jié)構(gòu)：相比于單鏈表和二叉排序樹的缺點(diǎn)，我們使用二叉堆這種結(jié)構(gòu)，它有兩個(gè)重要的性質(zhì)就是：

4.思想：

聲明：

#include <stdio.h>#include <stdlib.h>#define ElementType int/*優(yōu)先隊(duì)列數(shù)組實(shí)現(xiàn)*/typedef struct HeapStrcut	//堆結(jié)構(gòu){	int Capcity;	int Size;	ElementType *Elements;}*PRiorityQueue;PriorityQueue Initialize(int MaxElements);  //創(chuàng)建初始化優(yōu)先隊(duì)列void Insert(ElementType X, PriorityQueue H);//插入ElementType DeleteMin(PriorityQueue H);	    //刪除最小節(jié)點(diǎn)int IsEmpty(PriorityQueue H);		    //判斷優(yōu)先隊(duì)列是否為空int IsFull(PriorityQueue H);		    //判斷優(yōu)先隊(duì)列是否已滿實(shí)現(xiàn)：
/*創(chuàng)建初始化優(yōu)先隊(duì)列小頂堆，最小元在根節(jié)點(diǎn)*/PriorityQueue Initialize(int MaxElements){	PriorityQueue H;	//申請(qǐng)優(yōu)先隊(duì)列結(jié)構(gòu)空間	H = (PriorityQueue)malloc(sizeof(struct HeapStrcut));	if(NULL == H)	{ 		printf("Out of space./n");		exit(-1);	}	//申請(qǐng)存儲(chǔ)數(shù)據(jù)數(shù)組Elements空間	H->Elements = (ElementType *)malloc(sizeof(ElementType)*MaxElements);	if (H->Elements == NULL)	{		printf("Out of space./n");		exit(-1);	}	//初始化優(yōu)先隊(duì)列	H->Capcity = MaxElements;	H->Size = 0;}/*插入，交換而實(shí)施的賦值語句為d+1*/void Insert(ElementType X, PriorityQueue H){	int i;	if(IsFull(H))	{ 		printf("The PriorityQueue is full./n");		exit(-1);	}		for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2)		H->Elements[i] = H->Elements[i / 2];	H->Elements[i] = X;}//我的插入寫法，交換而實(shí)施的賦值語句為3dvoid Insert2(ElementType X, PriorityQueue H){	int i, tmp;	if (IsFull(H))	{		printf("The PriorityQueue is full./n");		exit(-1);	}	H->Elements[++H->Size] = X;	tmp = H->Elements[H->Size];	for (i = H->Size; i / 2 > 0; i /= 2)		if (H->Elements[i / 2] > H->Elements[i])			H->Elements[i] = H->Elements[i / 2];		else			break;	H->Elements[i] = tmp;}/*刪除最小節(jié)點(diǎn)*/ElementType DeleteMin(PriorityQueue H){	int i, child;	ElementType MinElement, LastElement;	if (IsEmpty(H))	{		printf("The PriorityQueue is empty./n");		exit(-1);	}	MinElement = H->Elements[1];	LastElement = H->Elements[H->Size--];	for (i = 1; i * 2 <= H->Size; i = child)	{		//查找較小的子節(jié)點(diǎn)		child = i * 2;		if (child != H->Size && H->Elements[child + 1] < H->Elements[child])			child++;		//下濾操作		if (LastElement > H->Elements[child])			H->Elements[i] = H->Elements[child];		else			break;	}	H->Elements[i] = LastElement;	return MinElement;}/*判斷優(yōu)先隊(duì)列是否為空*/int IsEmpty(PriorityQueue H){	return H->Size == 0;}/*判斷優(yōu)先隊(duì)列是否已滿*/int IsFull(PriorityQueue H){	return H->Size == H->Capcity;}/*顯示優(yōu)先隊(duì)列元素*/void show(PriorityQueue H){	int i;	for (i = 1; i <= H->Size; i++)		printf("%d/t", H->Elements[i]);	printf("/n");}int main(){	int max_elements, flag=1, choose, value;	//構(gòu)建優(yōu)先隊(duì)列	printf("開始構(gòu)建優(yōu)先隊(duì)列/n");	printf("請(qǐng)輸入優(yōu)先隊(duì)列大小：/n");	scanf("%d", &max_elements);	PriorityQueue H = Initialize(max_elements);		//優(yōu)先隊(duì)列操作	while (flag)	{		printf("請(qǐng)輸入操作，1.插入 2.刪除最小元 3.顯示優(yōu)先隊(duì)列元素./n");		scanf("%d", &choose);		switch (choose)		{		case 1:			printf("請(qǐng)輸入插入元素/n");			scanf("%d", &value);			Insert(value, H);			break;		case 2:			DeleteMin(H);			show(H);			break;		case 3:			show(H);			break;		default:			flag = 0;			break;		}	}    return 0;}
二、堆排序
1.思路：將要排序的數(shù)據(jù)構(gòu)建成小頂堆，交換根與最后節(jié)點(diǎn)，下濾重新構(gòu)建堆。
2.實(shí)現(xiàn)：
       數(shù)組實(shí)現(xiàn)，下標(biāo)從0開始：
/*堆排序思路：堆排序分為構(gòu)建堆、刪除最值、調(diào)整堆即上濾下濾操作。方法：使用數(shù)組代替ADT（抽象數(shù)據(jù)類型）的方式實(shí)現(xiàn)初始堆數(shù)組下標(biāo)從零開始。總結(jié)：時(shí)間復(fù)雜度為N*logN。*///上濾操作void PercDown(ElementType A[], int i, int N)	//i為父節(jié)點(diǎn)下標(biāo){	int replChild;		//下濾操作時(shí)用來與根節(jié)點(diǎn)交換的孩子節(jié)點(diǎn)下標(biāo)	ElementType tmp;	//一般利用交換進(jìn)行的排序都要有一個(gè)tmp變量	//每次開始都要取出最頂點(diǎn)下標(biāo)，所以可以寫在for語句頭中作為初始條件	//遍歷的條件就是父節(jié)點(diǎn)還有孩子	//執(zhí)行完此次下濾操作后需要找到下次下濾操作的父節(jié)點(diǎn)，所以我們也可以寫到for語句頭	for (tmp = A[i]; 2*i+1 < N; i = replChild)	//i = replChild是在語句體執(zhí)行之后執(zhí)行的	{		if (2 * i + 1 != N - 1 && A[2 * i + 1] < A[2 * i + 1 + 1])//若右孩子存在且右孩子大則將右孩子下濾			replChild = 2 * i + 1 + 1;		if (2 * i + 1 != N - 1 && A[2 * i + 1] > A[2 * i + 1 + 1])//若右孩子存在且右孩子小則將左孩子下濾			replChild = 2 * i + 1;		if(2 * i + 1 == N - 1)		//若右孩子不存在則將左孩子下濾				replChild = 2 * i + 1;		//書上方法		//replChild = 2*i+1;		//if (replChild != N - 1 && A[replChild + 1] > A[replChild])		//	replChild++;		//滿足孩子比父親數(shù)據(jù)大,將孩子數(shù)據(jù)賦值父親數(shù)據(jù),		//否則，不滿足堆結(jié)構(gòu)，不需要下濾跳出循環(huán)		if (tmp < A[replChild])			A[i] = A[replChild];		else			break;	}	A[i] = tmp;}//堆排序void HeapSort(ElementType A[], int N){	int i, temp;;	for (i = N / 2; i >= 0; i--)		PercDown(A, i, N);	for (i = N - 1; i > 0; i--)	{	//交換根與最后的節(jié)點(diǎn)數(shù)據(jù)		temp = A[0];		A[0] = A[i];		A[i] = temp;		PercDown(A, 0, i);	}}
3.分析：堆排序的時(shí)間復(fù)雜度為O（longN），構(gòu)建N個(gè)數(shù)據(jù)的二叉堆需要O（N）時(shí)間，DeleteMin需要O（NlogN）時(shí)間。
              堆排序是一個(gè)穩(wěn)定的排序，無論起始的數(shù)據(jù)序列是如何的。