堆排序

阿秀自己刷过的算法部分经过整理后是按照不同基础、不同人群分类的,如果你不知道自己该看哪个部分的算法题,可以先看一下这里,戳我直达

#

# 堆排序

看到两个比较好的讲解堆排序的B站视频

1、堆排序(heapsort) (opens new window)https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=3993837508839965022 (opens new window)

2、十分钟搞定堆排序 (opens new window)https://www.bilibili.com/video/BV1vt4y1y7wR?from=search&seid=3993837508839965022 (opens new window)

void heapify(vector<int>& nums, int n, int i)//对有一定顺序的堆,
//当前第i个结点取根左右的最大值(这个操作称heapfiy)
{
	int l = i * 2 + 1, r = i * 2 + 2;
	int max = i;
	if (l<n && nums[l]>nums[max])
		max = l;
	if (r<n && nums[r]>nums[max])
		max = r;
	if (max != i)
	{
		swap(nums[max], nums[i]);
		heapify(nums, n, max);
	}
}
void heapify_build(vector<int>& nums, int n)//建立大根堆,从树的倒数第二层第一个结点开始,
//对每个结点进行heapify操作,然后向上走
{
	int temp = (n - 2) / 2;
	for (int i = temp; i >= 0; i--)
		heapify(nums, n, i);

	for (int i = 0; i < nums.size(); i++)
		cout << nums[i] << " ";
	cout << endl;
}
void heapify_sort(vector<int>& nums, int n)//建立大根堆之后,每次交换最后一个结点和根节点(最大值),
//对交换后的根节点继续进行heapify(此时堆的最后一位是最大值,因此不用管他,n变为n-1)
{
	heapify_build(nums, n);
	for (int i = 0; i < n; i++)
	{
		swap(nums.front(), nums[n - i - 1]);
		heapify(nums, n - i - 1, 0);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36