跳转至

堆排序

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

堆排序

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

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

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

C++
 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
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);
    }
}