堆排序C语言实现

算法导论之堆排序，C语言实现版

#include 

// heap sort

int heapSize = 0;

#define SWAP_INT（ab） { a = a + b ; b = a - b ; a = a - b; }

/*
* Max-Heapify
* 
* l <-- LEFT（i）	
* r <-- RIGHT（i）
* if（l <= heap-size[A] and A[l] > A[i]）
*  then largest <-- l
*  else largest <-- i
* if（r <= heap-size[A] and A[r] < A[largest]）
*  then largest <-- r
* if largest != i
*  then exchange A[i] <--> A[largest]
*       Max-Heapify（Alargest）
*/

void MaxHeapify（int * arraySortint i）
{
	int l = 2*i+1;
	int r = 2*i+2;
	int largest = 0;

	if （l < heapSize && arraySort[l] > arraySort[i]）
	{
		largest = l;
	}
	else largest = i;

	if （r < heapSize && arraySort[r] > arraySort[largest]）
	{
		largest = r;
	}

	if （largest != i）
	{
		SWAP_INT（arraySort[i]arraySort[largest]）
		MaxHeapify（arraySortlargest）;
	}
}

void HeapSort（int * arraySortint arrayLen）
{
	//build max heap
	int i = arrayLen / 2;
	heapSize = arrayLen;

	for （ ; i >= 0 ; i--）
	{
		MaxHeapify（arraySorti）;
	}

	//sort
	for （i = arrayLen - 1 ; i >= 1 ; i--）
	{
		SWAP_INT（arraySort[0]arraySort[i]）
		heapSize--;
		MaxHeapify（arraySort0）;
	}
}

int main（）
{
	int arrarSort[10] = {4132169101487};

 	HeapSort（arrarSort10）;
 
	for （int i = 0 ; i < 10 ; i++）
	{
		printf（“%d“arrarSort[i]）;
	}

	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1329  2013-01-05 16:55  chapter6\chapter6\chapter6.cpp

     文件       3940  2013-01-05 15:49  chapter6\chapter6\chapter6.vcproj

     文件       1427  2013-01-05 16:57  chapter6\chapter6\chapter6.vcproj.VNKSKTWA366OGZL.Administrator.user

     文件     289792  2013-01-05 16:57  chapter6\chapter6.ncb

     文件        890  2013-01-05 15:49  chapter6\chapter6.sln

    ..A..H.      9216  2013-01-05 16:57  chapter6\chapter6.suo

     目录          0  2013-01-05 16:57  chapter6\chapter6

     目录          0  2013-01-05 16:57  chapter6

----------- ---------  ---------- -----  ----

               306594                    8