8644 堆排序

题目描述
Description
用函数实现堆排序，并输出每趟排序的结果

输入格式
第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式
第一行：初始建堆后的结果
其后各行输出交换堆顶元素并调整堆的结果，数据之间用一个空格分隔

输入样例
10
5 4 8 0 9 3 2 6 7 1

输出样例
9 7 8 6 4 3 2 5 0 1
8 7 3 6 4 1 2 5 0 9
7 6 3 5 4 1 2 0 8 9
6 5 3 0 4 1 2 7 8 9
5 4 3 0 2 1 6 7 8 9
4 2 3 0 1 5 6 7 8 9
3 2 1 0 4 5 6 7 8 9
2 0 1 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
 

#include
#define N 100

int A[N];
int length;
using namespace std;

void print()
{
	for (int z = 1; z <= length; z++)
		cout << A[z] << ' ';
	cout << endl;
}

void HeapAdjust(int A[], int k, int len)
{
	A[0] = A[k];//K为要调整的非终端结点。
	for (int i = 2 * k; i <= len; i *= 2)//注意此处的i*2意为调整一次后仍然没找合适位置那么 再看此时位置左孩子
	{
		if (i < len && A[i] < A[i + 1]) i++;//每次先指向左孩子,因为可能没有有孩子。

		if (A[0] >= A[i]) break;//筛选完毕。
		else
		{
			A[k] = A[i];
			k = i;//k可能插入的新位置
		}
	}
	A[k] = A[0];//将要调整的k插入应该插入的位置。
}


void BuildMaxHeap(int A[], int len)
{
	for (int i = len / 2; i > 0; i--)// len/2=第一个非终端（叶子节点）
	{
		HeapAdjust(A, i, len);
	}
}
void swap(int a, int b)//交换函数
{
	int t = A[a];
	A[a] = A[b];
	A[b] = t;

}

void HeapSort(int A[], int len)
{
	BuildMaxHeap(A, len);//首先创建大根堆。
	print();//打印此时第一次调整。
	for (int i = len; i > 1; i--)//从后向前调整。
	{
		swap(i, 1);
		HeapAdjust(A, 1, i - 1);//以1号结点为根节点的堆，不用再从下往上找了，因为经过第一次创建堆已经基本是大根堆，所以从根往下调整就可以了。
		print();
	}

}
int main()
{
	cin >> length;
	for (int i = 1; i <= length; i++)
		cin >> A[i];
	HeapSort(A, length);
	return 0;
}