【排序算法】堆排序详解与实现

一、堆排序的思想

二、堆排序的图解

下图以建大堆为例排一个升序序列

三、堆排序的实现

3.1向下调整算法的实现

实现堆排序最重要的就是实现向下调整算法。以下是向下调整算法的代码以及解释

//这里以建大堆为例
void AdjustDown(int* a, int n, int root)
{
	int child = root * 2 + 1;//找到根节点的左孩子
	while (child < n)//判断左孩子是否出界
	{
		if (child + 1 < n && a[child + 1] > a[child])
			//child + 1 < n判断右孩子是否出界，
			//a[child + 1] > a[child]判断左右孩子的大小，取左右孩子中大的那一个
			child++;
		if (a[child] > a[root])//入过孩子的值比父亲的值大，就交换孩子和父亲的位置
			Swap(&a[child], &a[root]);
		else//如果孩子的值不比父亲的值大，就证明大堆已经建好了（因为此时父亲的左右子树都是大堆），
			//直接break跳出循环。
			break;
		//没有break来到这里就顺着子树继续往下走
		root = child;
		child = root * 2 + 1;
	}
}

3.2堆排序的实现

以下是堆排序的代码实现以及解释

void HeapSort(int* a, int n)
{
	//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		//(n - 1 - 1) / 2找到第一个非叶子节点，从第一个非叶子结点开始向下建堆
		AdjustDown(a, n, i);
	}
	//堆建好了
	int end = n - 1;
	while (end > 0)
	{
		//假设是建大堆，将下标为0的元素和下标为end的元素交换，
		//最大的数就排到最后了，也就相当于最后的那个数已经排好了，不用再参与下面的向下建堆
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);//还没有排好的数向下建堆从0位置开始向下建堆
		end--;
	}
}

四、总结