常用排序算法的实现（C语言版）-堆排序

堆排序：

/**
*排序过程中使用到的堆的结构
*/
typedef struct heap {
	int heapSize;
	int *ap;
	int apLength;
} Heap;

/*
*调整i位置上的元素，以保持最大堆的性质
*/
void maxHeapify(int a[], int i, int hSize) {
	int l, r, largest;
	l = 2 * i + 1;
	r = l + 1;

	if (l < hSize && a[l] > a[i]) {
		largest = l;
	} else {
		largest = i;
	}

	if (r < hSize && a[r] > a[largest]) {
		largest = r;
	}

	if (largest != i) {
		swap(a, i, largest);
		maxHeapify(a, largest, hSize);
	}
}

/*
*构建最大堆
*/
Heap buildMaxHeap(int a[], int n) {
	Heap hp;
	int i;

	hp.ap = a;
	hp.heapSize = n;
	hp.apLength = n;

	for (i = n / 2 - 1; i >= 0; i--) {
		maxHeapify(a, i, n);
	}
	return hp;
}

/*
*堆排序算法
*/
void heapSort(int a[], int n) {
	int i;
	//build max-heap
	Heap heap = buildMaxHeap(a, n);

	for (i = n - 1; i > 0 ; i--) {
		swap(a, i , 0);
		heap.heapSize--;
		maxHeapify(a, 0, heap.heapSize);
	}

}