T233293 【模板】堆排序

题目描述

利用堆排序算法将读入的 N 个数从小到大排序后输出。

输入格式

第 11 行为一个正整数 N，第 22 行包含 N 个空格隔开的正整数 ai​，为你需要进行排序的数，数据保证了 Ai​ 不超过 109109。

输出格式

将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

5
4 2 4 5 1

1 2 4 4 5

说明/提示

对于 20% 的数据，有 N≤103；

对于 100% 的数据，有 N≤105。

题解

首先将待排序的数组构造成一个大根堆。将无序的序列看成一个堆结构，将序列里的值按照从上往下，从左往右的顺序依次填充到二叉树中。接着，找到一个非叶子节点，比较它的左右节点中最大的一个的值，如果比它大，就交换位置。不断重复这一步骤，直到构造出一个大根堆。

接下来进行排序。首先将顶端元素和末尾元素交换，交换后末尾元素不变，剩余元素重构大根堆。经过不断的重复，最后得到最终的排序结果。

#include <iostream>

using namespace std;
void HeapAdjust(int* a, int start, int end)
{
    int tmp = a[start];
    for (int i = 2 * start + 1; i <= end; i = i * 2 + 1)
    {
        if (i < end&& a[i] < a[i + 1])
        {
            i++;
        }
        if (a[i] > tmp)
        {
            a[start] = a[i];
            start = i;
        }
        else
        {
            break;
        }
    }
    a[start] = tmp;
}
void HeapSort(int* a, int n)
{
    for(int i=(n-1-1)/2;i>=0;i--)
    {
        HeapAdjust(a, i,n - 1);
    }
    int tmp;
    for (int i = 0; i < n - 1; i++)
    {
        tmp = a[0];
        a[0] = a[n - 1-i];
        a[n - 1 - i] = tmp;
        HeapAdjust(a, 0, n - 1-i- 1);
    }
}
int main()
{
    int n,i,j,t,k;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    HeapSort(a,n);
    for(i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}