【数据结构】—

【数据结构】——堆排序

前言：我们已经学习了堆以及实现了堆，那么我们就来给堆进行排序。我们怎么来进行排序呢？这一次我们就来解决这个问题。

在这里插入图片描述

如果我们堆排序要求排序，我们是建立大堆还是小堆呢，如果我们建的小堆的话，那我们在排序的时候就给不断地进行建堆，那么我们的时间复杂度就会很大，如果我们建立大堆的话，最大的数就在堆顶，如果我们要给接下来的排序，我们要求排升序的话我们的大堆就可以很简单的解决这个问题，我们只需要把堆顶的数和最后一个数进行交换在不断地进行向下调整就可以了。时间复杂度就很小，所以我们排升序就建立大堆。

建立大堆：

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


void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
			//child = (child - 1) / 2;
			//parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

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)
{
	 //建大堆
	 //O(N*logN)
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

我们的end是最后一个元素下标，是前面的元素的个数，我们就让它与堆顶元素交换在向下调整，调整完之后就让end–，也就是堆顶与下标为n-2的元素交换，在进行调整，反复操作知道end<=0结束。

我们建立大堆的代码还可以改进优化到时间复杂度为O(N)：

void HeapSort(int* a, int n)
{
	 //建大堆
	 /*O(N)*/
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

因为我们的父节点下标为子节点下标减去1再除以2，所以我们可以直接利用循环传参的是父节点的下标，所以我们的这个方法是先从最下面的父节点开始调整，最后在调整下标为0的父节点。

接下来我们就来测试我们代码：

int main()
{
	int a[] = { 4, 6, 2, 1, 5, 8, 2, 9 };

	HeapSort(a, sizeof(a)/sizeof(int));

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

	return 0;
}