堆排序

总结:因为堆里面第一个是最小的或者是最小的，所以我们可以挨个取出来，然后再重新排序，最后排序成功

#include<stdio.h>
#include<stdlib.h>
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void heapify(int tree[], int n, int i) //i表示的是要对哪个节点做操作，n表示由多少个节点
{
if (i >= n) //出口
return;
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;//假设一个最大的节点
if (c1<n && tree[c1]>tree[max])//防止越界
{
max = c1;
}
if (c2<n && tree[c2]>tree[max])//防止越界
{
max = c2;
}
if (max != i)//这里就是防止一个数的下标是i的数本身就是最大的，防止自己交换自己
{
swap(tree, max, i);
heapify(tree, n, max);
}
}

void build_heap(int tree[], int n)
{
	int last_node = n - 1;
	int parent = (last_node - 1) / 2;
	for (int i = parent; i >= 0; i--)
	{
		heapify(tree, n, i);
	}
}
void heap_sort(int tree[], int n)
{
	build_heap(tree, n);
	int i;
	for (i = n - 1; i >= 0; i--)
	{
		swap(tree, i, 0);//与第一个交换
		heapify(tree, i, 0);//这里的i本来是n的，但是n一直再变化,所以写i就可以了
	}
 }

int main(void)
{
int tree[] = { 4,10,3,5,1,2 };
int n = 6;
//heapify(tree, n, 0);//一共0个节点我们对第0个节点做这个操作
heap_sort(tree, n);
for (int i = 0; i < 6; i++)
{
printf("%d ", tree[i]);
}
system(“pause”);
return 0;
}