堆排序

teach

堆排序实现及讲解

堆排序

代码核心思想

其实只要你的程序保证两点，代码就可以正确运行

1.根节点是最大的
2.对图中所有的树而言，左子树和右子树是整棵树次大和第三大的数（最重要的）

我想说的是，堆排序已经有一种线段树的思想在里面了，只要加上延迟标记，它就是一棵线段树。

做法

大顶堆：
一开始从树的最下方开始对每个节点的子树进行操作，使得左子树和右子树中最大的数和该子树根节点比较，如果是比根节点大的就交换，并且交换后将被换下来的根节点向下做同样操作。
如果是根节点最大，就不用继续向下比较了，因为下面的子树都满足了上述条件。
到达二叉树的根节点之后，将根节点输出，然后将根节点和最后一个节点的数交换，并删除最后一个节点。
对二叉树的根节点做一开始的操作，即：根节点的左右子树选出最大和根节点比较，根节点若比该数更小则交换，同时被向下交换后的根节点就跟它的新左右子树进行同样操作，直到无法操作。

代码

1
2
3
4
5
6
7
#include<iostream>
#include<cstdio>
#include<algorithm>
#define rep(i,a,n) for(int i=a; i<n; i++)
#define rep1(i,a,n) for(int i=n-1; i>=a; i--)
#define s(a) scanf("%d",&a)
using namespace std;
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
int a[100];
void down(int x,int n)
{
    int temp=a[x];
    int j=x*2+1;
    while(j<n)
    {
        if(j+1<n&&a[j]<a[j+1])
           j++;
        if(a[j]>temp)
            a[x]=a[j];
        else break;
        x=j;
        j=x*2+1;
    }
    a[x]=temp;
}
int main()
{
    int n;
    s(n);
    rep(i,0,n)
      s(a[i]);
    rep1(i,0,n)
      down(i,n);
    rep1(i,0,n)
    {
        down(0,i+1);
        rep(j,0,n)
          printf("%d ",a[j]);
        printf("\n");
        int temp=a[i];
        a[i]=a[0];
        a[0]=temp;
    }
}