堆排序(heap sort)

虽然知道算法的基本原理，还是动手写写吧。

代码如下：

#include <stdio.h>
#include <stdlib.h>

void MaxHeapfy(int *array, int i, int heapSize)
{
	int l, r ;
	int temp, largest;
	l = 2 * i;
	r = 2 * i + 1;
	if(l <= heapSize && array[l] > array[i])
		largest = l;
	else
		largest = i;
	if(r <= heapSize && array[r] > array[largest])
		largest = r;
	if(largest != i)
	{
		temp = array[i];
		array[i] = array[largest];
		array[largest] = temp;
		MaxHeapfy(array, largest, heapSize);
	}
}

void BuildMaxHeap(int* array, int n)
{
	int heapSize = n;
	int i;
	for(i=n/2; i>=1; i--)
		MaxHeapfy(array, i, heapSize);
}

void HeapSort(int *array, int n)
{
	int temp;
	int heapSize = n;
	int i;
	BuildMaxHeap(array, n);
	for(i=n; i>=2; i--)
	{
		temp = array[1];
		array[1] = array[i];
		array[i] = temp;
		heapSize--;
		MaxHeapfy(array, 1, heapSize);
	}
}

int main()
{
	int *array;
	int n;
	int i;
	
	while(scanf("%d",&n) != EOF)
	{
		array = (int*)malloc(sizeof(int)*(n+1));	//the index starts from 1
		for(i=1; i<=n; i++)
			scanf("%d",array+i);
		
		HeapSort(array, n);
		
		for(i=1; i<=n; i++)
			printf("%d ", array[i]);
		printf("\n");
	}	
	return 0;
}

PS：喜欢上Scribes Text Editor，虽然没有Vim, Emacs那般强大，但写写小程序够用了，之前试过很多编辑器，发现不是很简便，终于找到一个喜欢的了……