5.堆排序

5.1 描述
（1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
（2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),
     且满足R[1,2…n-1]<=R[n]；
（3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，
然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成 

5.2 复杂程度
时间复杂度O(nlog2n)                 
空间复杂度O(1)

5.3 代码
#include <stdio.h>
void swap(int arr[], int a, int b)
{
	int tmp;
	tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}

void heapify(int tree[], int n, int i)
{
	if (i >= n)
	{
		return;
	}
	int max = i;//假设父节点为最大值
	int c1 = 2 * i + 1;
	int c2 = 2 * i + 2; //左孩子结点的下标为2i + 1, 右孩子结点的下标为2i + 2
	if (c1 < n && tree[c1] > tree[max])
	{//左孩子的下标要小于总结点数
		max = c1;//将较大值的结点下标记录下来
	}
	if (c2 < n && tree[c2] > tree[max])
	{
		max = c2;//将较大值的结点下标记录下来
	}
	if (max != i)
	{//如果最大值不是根节点
		swap(tree, max, i);//交换tree[max]和tree[i]的值
		heapify(tree, n, max);//max就是孩子结点下标
	}
}

void build_heapify(int tree[], int n)
{
	int last_node = n - 1;
	int parent = (last_node - 1) / 2;
	int i;
	for (i = parent; i >= 0; i--)
	{
		heapify(tree, n, i);
	}
}

void heapify_sort(int tree[], int n)
{
	build_heapify(tree, n);
	int tmp = tree[0];
	for (int i = n - 1; i >= 0; i--)
	{//从最后一个结点开始
		swap(tree, i, 0);
		heapify(tree, i, 0);
	}
}

int main(){
	int tree[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
	int n = 14;
	printf("原数组为:");
	for (int i = 0; i < n; i++)
	{
		printf("%d ", tree[i]);
	}
	printf("\n");
	heapify_sort(tree, n);
	printf("经过堆排序后的数组为：");
	for (int i = 0; i < n; i++)
	{
		printf("%d ", tree[i]);
	}
	printf("\n");
	return 0;
}

5.4 运行时间
0.02498s