数据结构——堆排序

数据结构——堆排序

排序方法很多，各有优势，我们常用的排序方法是属于内部排序的，对辅助空间的使用很少，而时间复杂度可能遇到了限制了，我所知道几种排序方法最快也没有突破nlogn 这个限制。对于平均时间复杂度来说，快速排序已经是这种算法的佼佼者了，但是它的最坏情况恐怕是不能接受的，n2 ；这里推荐一种稍微复杂的排序，叫做堆排序，它基于一种数据结构——堆。才有了很小的时间复杂度，同时又有很稳定的特性。

先介绍一下堆的定义：

​ 一颗二叉树，任意非叶子节点的左右子节点都同时比它大，或者同时比它小。

表现在数组中是这样的：

​ 一串n个元素的序列，a1,a2,...,an ，下标由1开始；

{ki≤k2iki≤k2i+1

或{ki≥k2iki≥k2i+1

(i=1,2,...,n/2.)

堆的定义有很明显的作用，最小的或者最大的数字永远在堆顶，对吗？这样子每次能够从堆顶拿出一个数字，并且从堆里面删去这个数字，再拿，如此往复，组成一个序列不就是一个有序的数组吗？并且用时是n 。很美好。但是维护一个堆删除了堆顶的数字依然有序这是需要代价的，你需要调整几乎一个堆，从上至下。让数字的位置又满足堆的定义。

重新调整堆的方法叫做“筛选”，是这样的：

假设一个标准的堆，拿出了堆顶的元素，要删除堆顶的元素；

拿出13 ，把97放到堆顶，
97破坏了以1节点下的堆，所以交换1节点和它的子节点，选择2，3节点中小的那一个交换，那就是27这个3节点，这样子1节点下的堆就维护好了，但是破坏了3节点下的堆。所以依法炮制，换3节点和它的子节点。直到没得换了。

接下来再拿出堆顶元素，27.并且维护下堆，如上方法：

还有个问题没解决的，就是初始的时候建立一个堆。

很简单的一棵树由下往上，可以生成堆的节点，也就是有子节点的节点就“筛选”一下就可以形成堆。

这个图片是借用一下别人的，所以数字不同于上面的了，但是是一个思路，在这只做演示使用。（画图有点累啊）！！

很详细了。按图索骥都成了，所以贴代码了。

#include<cstring>
#include<cstdio>

using namespace std;

void HeapAdjust(int a[],int s,int e)
{
    int length = e-s;
    int rc=a[s];
    for(int i=2*s;i<=e;i*=2)
    {
        if(i<e &&a[i]<a[i+1])
            i++;
        if(a[i]<rc)
            break;
        a[s] = a[i];
        s=i;
    }
    a[s] = rc;
}

void HeapSort(int a[],int length)          //a数组必须由下标1开始储存
{
    for(int i=length/2;i>0;i--)
    {
        HeapAdjust(a,i,length);
    }
    int t;
    for(int i=length;i>1;i--)
    {
        t=a[i];
        a[i]=a[1];
        a[1]=t;
        HeapAdjust(a,1,i-1);
    }
}
int main()
{
    int a[10]={0,49,38,65,97,76,13,27,49};
    HeapSort(a,8);
    for(int i=1;i<=8;i++)
        printf("%d ",a[i]);
    return 0;
}