编辑代码

#include<stdio.h>

void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整算法
void AdjustDown(int* arr, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//默认先对左孩子进行操作
	while (child<n)
	{
		//选出左右孩子较小的那一个
		//防止没有右孩子，数组越界
		if (child+1<n && arr[child + 1] > arr[child]) //建小堆用小于，建大堆用大于
		{
			child += 1;
		}

		if (arr[child] > arr[parent]) //建小堆用小于，建大堆用大于
		{
			Swap(&arr[child], &arr[parent]);//交换父子的值
			parent = child;//父亲到孩子的位置，继续向下调整
			child = parent * 2 + 1;//默认又从左孩子开始
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* arr, int n)
{
	//建堆,排升序建大堆，排降序建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	//排升序
	int end = n - 1;//end为最后一个数的下标
	while (end > 0)//剩余超过一个数就交换
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

void test()
{
	int arr[] = { 10,9,8,7,6,5,3,5,4,2,0,1 };
	int n = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, n);
	Print(arr, n);
}

int main()
{
	test();
	return 0;
}