堆排序——C/C++

2023-12-16 10:37:21

????????之前总是想不通堆排序因为很抽象,抽象的地方在于,它要排序的是一个数组,物理上排序的动作确是在二叉树上(准确地来说是平衡二叉树)。

????????堆排序要做的首先是要构造出一个小根堆(小根堆的特点就是根节点小于左右子树)或者大根堆。小根堆最后排成降序,大根堆排成升序。

? ? ? ? 构造好小根堆的时候,最小值已经在根节点上了,这时把根节点的值和最后一个节点(数组0下标和n-1下标)交换,这样就破坏了这个小根堆,然后继续把它调整成小根堆,这次调整的时候就不带上n-1下标这个值了,然后又可以找出整个数组的第二小值,以此类推就可以找到第三小值......第n-1小值,就不用再调整了这时就剩一个最大值了。

????????

? ? ? ? ? ???

? ? ? ? ? ??

?

//把小的值向上调整
//                              开始调整的起始位置,终止位置
void FilterUp(vector<int>& nums, int start, int end)
{
	int i = start, j = i * 2 + 1;//j是i的左子树
	int tmp = nums[i];
	while (j <= end)
	{
		if (i<end && nums[j]>nums[j + 1]) j += 1;//把j放在小的那一个节点上
		//因为小根堆的宗旨是遍寻最小值把它顶上去
		while (j < end)//j>end就退出循环结束比较
		{
			if (nums[j] >= tmp) break;//i作为根节点的子树已经是小根堆
			else//否则如果j位置的值比上面i小就要调整了
			{
				nums[i] = nums[j];
				i = j;//i往下走
				j = i * 2 + 1;//j往下走,直到没有数据
			}
		}
	}
	nums[i] = tmp;//把tmp的值放在i位置
}

void HeapSort(vector<int>& nums, int n)//n表示数组长度
{
	if (n < 2) return;//0/1个元素就不用排了
	//先把它变成小根堆
	int pos = (n - 2) / 2;//n-1是最后一个元素的下标,再-1除2就是它的父节点下标
	while (pos >= 0)//示例数组从3号下标的子树开始,再2号,再1号,再0号
	{
		FilterUp(nums, pos, n - 1);//从下往上
		pos--;
	}
	pos = n - 1;
	while (pos > 0)//n个元素只需要排n-1次就能得到结果
	{
		swap(nums[0], nums[pos]);
		pos--;
		FilterUp(nums, 0, pos);//因为已经把它排成小根堆了,所以这次从根节点开始往下找最小的就行
	}
}

(从1->4调整(3到0下标))?

文章来源:https://blog.csdn.net/qq_60012598/article/details/134959438
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。