堆排序

代码

#include<iostream>
#define N 9
#define ElemType int
void AdjustDown(ElemType A[], int k, int len) {
	int i;
	A[0] = A[k];//A[0]暂存
	for (i = 2 * k; i <= len; i *= 2) {
		if (i < len&&A[i] < A[i + 1])
			i++;
		if (A[0] >= A[i])
			break;
		else {
			A[k] = A[i];
			k = i;
		}
	}
	A[k] = A[0];
}
/*建立大根堆*/
void BuildMaxHeap(ElemType A[], int len) {
	for (int i = len / 2; i > 0; --i) {
		AdjustDown(A, i, len);
	}
}
/*堆排序*/
void HeapSort(ElemType A[], int len) {
	ElemType x;
	int i;
	BuildMaxHeap(A, N - 1);
	for (i = len; i > 1;--i) {
		x = A[i];
		A[i] = A[1];
		A[1] = x;
		AdjustDown(A, 1, i - 1);
	}
}
/*输出数组*/
void OutPrint(ElemType A[]) {
	int i;
	for (i = 1; i < N; i++)
	{
		printf("%d  ", A[i]);
	}
}
int main() {
	ElemType A[N] = { -1,48, 62, 35, 77, 55,14,35,98 };
	printf("排序前数组
");
	OutPrint(A);
	HeapSort(A, N - 1);
	//BuildMaxHeap(A, N-1);
	printf("
排序后数组
");
	OutPrint(A);
	system("pause");
	return 0;
}

结果如图：