数据结构-堆排序问题

需要在数组里面进行排序，我们可以采取堆排序对其解决问题

版本1：

创建一个数组等大的堆，把数组里面的数值输入到堆里面进行堆排序，但是这样的弊端就是，不是顺序排序

版本2：

每次我们取堆顶然后打印，最后出堆，循环

弊端就是这样是时间复杂度我们发现还是o(n)，没有必要那么麻烦半天时间复杂度还是这样

版本3:（推荐）

在数组上面进行排序，直接输出顺序排序

逻辑讲解

1，需要在数组里面进行排序，我们可以采取在数组建堆

2，然后交换收尾元素，每次调整的数值减少1

讲解逻辑

首先我们需要知道，

如果我们需要排序的是降序，我们就需要建立小堆

如果我们需要排序的是升序，我们就需要建立大堆

如果我们需要的是升序建立小堆的话

如果我们采取相反的方式的话，就会导致：（出现两个根）

首先n个数建小堆，固定第一个值是最小值
剩下的n-1个数再建堆
效率就很差了

如果相反的话，会导致根节点变化，从而导致逻辑混乱，数组里面的数值少的时候是不明显的，但是多的时候就不行了

逻辑实现图解

代码实现

//向下调整（大堆）
void AdjustDown(HPDataType* a, int n, int parent)
{
	int chile = parent * 2 + 1;
	//循环条件不能是父亲，不然会导致越界
	while (chile < n)
	{
		//三个孩子进行比较
		if (chile + 1 < n && a[chile] < a[chile + 1])
		{
			chile++;
		}
 
		if (a[chile] > a[parent])
		{
			Swap(&a[chile], &a[parent]);
			parent = chile;
			chile = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//堆排序数组内进行调整解决
void sort_test(int* a, int sz)
{
	//放出来的是小堆，所以我们只能排序降序，这样逻辑更融洽
	//建堆
	for (int i = 0; i < sz; i++)
	{
		AdjustUp(a, i);
	}
	//交换排序 把首个元素和最后一个交换进行排序 每次--
	while (sz > 0)
	{
		Swap(&a[0], &a[sz - 1]);
		AdjustDown(a, sz - 1, 0);
		sz--;
	}
}

这个 sort_test 函数实现了一个堆排序算法，它接收一个整数数组 a 和它的大小 sz：

1. 建堆：首先，函数通过调用 AdjustUp 函数来构建一个小顶堆（最小堆）。建堆过程是从最后一个非叶子节点开始向上调整，直到堆顶。

2. 交换和排序：在建堆之后，函数进入一个循环，每次循环中，它将堆顶元素（当前堆中的最小元素）与当前堆的最后一个元素交换。然后，堆的大小减少 1，并且对剩余的堆进行向下调整以保持最小堆性质。

3. 循环结束：循环继续进行，直到堆的大小减小到 0。最终，数组 a 将被排序为降序。