本文共 1815 字，大约阅读时间需要 6 分钟。

#include "stdafx.h"int arrNum[10] = {2,44,3,55,6,77,3,5,222,0xa};#define LEFT(i) (2 * (i))#define RIGHT(i) ((2*(i)) + 1 )#define PARENT(i) ((i)/2)/*  * 建立符合堆性质的子堆 * * arr：堆 * start：要整理的堆的首元素 * size：整个堆的大小，用来判断首元素或者中间元素是否已经越界，即代码中的 l < size.... * * 比较堆中首元素和其两个子女的大小，找到最大元素。 * 如果最大元素是首元素，则无需调整。 * 如果最大元素不是首元素，则交换最大元素和首元素。 * 交换后，首元素的位置下移，可能会破坏子堆的性质，需要递归调用max_heaify。 * */void max_heapify(int *arr, int start, int size){	int l = LEFT(start);	int r = RIGHT(start);	int largest = start;	int swap = 0;	//比较堆中首元素和其两个子女的大小，找到最大元素。	if(l <= (size) && arr[l-1] > arr[start-1])	{		largest = l;	}	if(r <= (size) && arr[r-1] > arr[largest-1])	{		largest = r;	}	//如果最大元素是首元素，则无需调整。	//如果最大元素不是首元素。	if(largest != start)	{		//则交换最大元素和首元素		int temp = arr[start-1];		arr[start-1] = arr[largest-1];		arr[largest-1] = temp;				//交换后，首元素的位置下移，可能会破坏子堆的性质，需要递归调用max_heaify。		max_heapify(arr, largest, size);	}}/*  * 建堆 * * arr：堆 * size：整个堆的大小 * * 从第一个有子节点的堆元素开始（即堆长度/2处）。 * 循环调用max_heapify。 * */void build_heap(int *arr, int size){	int i = 0;	//从第一个有子节点的堆元素开始（即堆长度/2处）。	for(i = size/2; i > 0; i--)	{		//循环调用max_heapify，首元素每次循环改变。		max_heapify(arr, i, size);	}}/*  * 堆排序 * * arr：堆 * size：整个堆的大小 * * 首选建堆。 * 建堆后堆顶即为最大元素，交换最大元组到堆尾。 * 改变堆的大小，做-1操作，这样就等于找到了最大元素。 * 交换后，堆顶的元素可能破坏堆性质，重新调整堆元素的顺序，使之符合堆性质。 * 继续交换堆顶元素到堆尾（这时的堆尾由于刚才的-1操作，已经是数组的倒数第二的位置） * 循环持续缩小堆，直至排序完成。 * */void heap_sort(int *arr, int size){	int temp = 0;	//首选建堆。	build_heap(arr, size);	//循环持续缩小堆，直至排序完成。	for(int i = size; i > 1; i--)	{		//建堆后堆顶即为最大元素，交换最大元组到堆尾。		temp = arr[0];		arr[0] = arr[i-1];		arr[i-1] = temp;		//交换后，堆顶的元素可能破坏堆性质，重新调整堆元素的顺序，使之符合堆性质。		max_heapify(arr, 1, i - 1);	}	return;}int _tmain(int argc, _TCHAR* argv[]){	int size = sizeof(arrNum)/sizeof(int);	heap_sort(arrNum, size);	for(int i = 0; i < size; i++)	{		printf("%d,", arrNum[i]);	}	printf("\n");		return 0;}

转载地址：http://aoyni.baihongyu.com/