【数据结构】学了数据结构还不会堆排序？--堆排序超详解

用户9645905

发布于 2022-11-30 12:40:51

3070

发布于 2022-11-30 12:40:51

文章被收录于专栏：Linux学习~

前言

在数据结构中我们学了堆的性质及其实现，而这里我们将讲解用堆来实现排序

背景

对给定数组进行堆排序，排成降序

排序策略

排序原则

如果是排升序那么则先将给定数组建立大堆如果是排降序那么则先将给定数组建立小堆
注：这里排成降序，我们数组建立成一个数组小堆，对于大堆稍作修改就行了

如何建小堆数组

根位置和左右子位置下标关系：

leftchild=root*2+1; rightchild=root*2+2; (leftchild(rightchild)-1)/2=root;
我们依据下标关系，可以找到对应的根位置或者子位置并操作数据建立成堆

建堆策略1：向上调整

对每个数据进行向上调整直到符合小堆
当前位置数据和根位置数据比较，如果不符合小堆则交换，直到向上调整到符合小堆
这里我们可以从第二个数据开始调整，也可以从最后一个数据开始调整

图示过程：从尾部数据往前开始向上调整

建堆策略2：向下调整

对每个位置数据的根位置数据进行向下调整
根位置和数据较小的子位置比较，不符合大堆则交换，直到符合
然而对数据使用向下调整的前提是，根的左右子堆都符合大堆
所以我们从最后一个数据的根位置开始进行调整，直到堆顶数据调整完毕

图示过程：

建成小堆之后

我们都知道小堆堆顶的数据永远是当前堆中数据最小的
我们让堆顶的数据与堆尾数据进行交换（最小的数就排到了最后）
交换后将除现堆尾的数据看成一个堆
对交换后的堆顶数据进行向下调整（调整后又成小堆）
调整后的堆顶数据是当前堆中（包括排除在外的堆尾的最小数）次小的数
让该堆顶数据与堆倒数第二个数据交换
以此循环直到交换到堆的正数第二个数据，这个数组降序也就排序好了

过程示图：

参考代码：

//数据调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child<size)
	{		
		//找到数据小的儿子
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		
		//将父节点与小子节点交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);//交换数据
			parent = child;//调整下标位置
			child = parent * 2 + 1;
		}
		else
		{
			break;//结束调整
		}
	}
}

// 对数组进行堆排序
void HeapSort(int* a, int n)
{
	//排降序，建立小堆（小堆堆顶数据一定是最小的）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//建堆：从最后一个数据的父节点进行向下调整一直到最开始数据
	{
		AdjustDown(a, n,i);
	}
	//将堆顶数据放与末尾数据交换，再将除最小数据外的数组看成堆
	//对当前顶数据调整，调整后当前堆的最小数据处在堆顶位置
	//以此循环，每次最小的数据都放在当前堆的最后面，最终也就成了降序
	for (int end = n - 1; end >= 0; end--)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
	}
}

测试

测试代码：

int main()
{
	int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	HeapSort(a, sizeof(a) / sizeof(a[0]));

	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}