堆排序的讲解与代码（C语言）实现

1.对与堆排序我们不必先去实现一个堆，将数组的元素一个一个插进去，我们可以知道数组是一个完全二叉树的结构，所以可以直接在数组上建堆。

 2.如果是排升序，我们可以建小堆找出最小的数。

 找到最小的数为10，如何找到次小的数呢？如果从12开始剩下的看作一个堆，之前建立的堆关系就全都乱了，这时需要重新建立小堆，才能选出次小的数！这样的效率太低了！

换一种思路，我们建大堆排升序。建大堆选出最大的数，将最大的数与最后一个数交换，把最后一个数不看做堆里，从堆顶向下调整，以此类推就实现排序了。（如果我们要实现降序的话就是建一个小堆。改为建小堆只需要将向下调整函数中的选择交换哪一个数的条件改为小于）。

#include 
#include
void HeapSort(int *a, int size)
{
	//排升序建大堆
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		//找到叶子节点的父亲依次向下调整
		AdjustDown(a,size, i);
	}
	//将堆顶数值与最后的数交换，在向下调整
	for (int end = size - 1; end > 0; end--)
	{
        //交换数值
		Swap(&a[0], &a[end]);
        //向下调整
		AdjustDown(a, end, 0);
	}
}
//交换数值
void Swap(int *px, int*py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
//向下调整
void AdjustDown(int *a,int n,int parent )
{
	assert(a);
    //找到叶子节点的父亲
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n  && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child]>a[parent])
		{
			//交换数值
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int arr[10] = { 12, 20, 77, 10, 32, 56, 24, 70, 15, 45 };
    //打印排序前的数组
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ", arr[i]);
	}
	printf("n");
	HeapSort(arr,sizeof(arr)/sizeof(int));
    //打印排序完的的数组
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}

运行结果：

以上是堆排序的讲解与代码实现。

感谢看到这里的老铁，如果文章有用的话请给我一个赞支持一下，感激不尽！

在下才疏学浅，一点浅薄之见，欢迎各位大佬指点。