堆排序 HeapSort

一、简介：堆即子结点的键值或索引总是小于（或者大于）它的父节点的二叉树。堆排序就是先将序列构造成堆，再利用堆的性质，第一个元素即是最大（或最小）的元素，进行排序。

二、代码

　　1、heapadjust函数，用于将序列调整为堆

/*l是待排序的数组，这个函数是让l[s..m]成为一个大顶堆*/
void heapadjust(int *l,int s,int m)
{
    int i,temp;

    temp=l[s];
    for(i=2*s;i<=m;i*=2)
    {
        if(i<m&&l[i]<l[i+1])
        {
            i++;          /*l[s]的左孩子l[i]和右孩子l[i+1] 如果小于,执行此语句，让l[i]指向较大的孩子*/
        }
        if(temp>=l[i])      //再比较堆顶元素和孩子节点中较大孩子的大小
            break;　　　　　　
        l[s]=l[i];
        s=i;
    }
    l[s]=temp;
}

　　2、heapsort函数：将堆顶元素（即是最大元素）取出来，再调整新的堆，重复这个过程，就完成了排序

void swap(int *l,int a,int b)
{
    l[0]=l[a];
    l[a]=l[b];
    l[b]=l[0];
}

void heapsort(int *l,int lenght)
{
    int i;

/*先让数组l成为大顶堆*/
    for(i=lenght/2;i>0;i--)
    {
        heapadjust(l,i,lenght);
    }


    for(i=lenght;i>1;i--)
    {
        /*交换当前未排序的大顶堆第一个(最大的元素)和最后一个(最小的元素)*/
        swap(l,1,i);        /*注意此处是 i 而不是 lenght ，l[i]即是当前未排序的最后一个元素*/
        heapadjust(l,1,(i-1));
    }
}

下面是测试代码：随机生成序列，并排序

/*这个算法，画图比较好理解*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define NUM 100

void heapadjust(int *l,int s,int m);
void swap(int *l,int a,int b);      //交换数组中第a和第b个元素
void heapsort(int *l,int lenght);

int main()
{
    int i,a[NUM+1];

    srand((unsigned)time(NULL));
    /*a[0]作为哨兵单元，不在随机数生成之列*/
    for(i=1;i<=NUM;i++)
    {
        a[i]=rand();
    }

    printf("Befor sort:");
    for(i=1;i<=NUM;i++)
    {
        printf("%d ",a[i]);
    }

    heapsort(a,NUM);

    printf("
After sort:");
    for(i=1;i<=NUM;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}

/*l是待排序的数组，这个函数是让l[s..m]成为一个大顶堆*/
void heapadjust(int *l,int s,int m)
{
    int i,temp;

    temp=l[s];
    for(i=2*s;i<=m;i*=2)
    {
        if(i<m&&l[i]<l[i+1])
        {
            i++;          /*l[s]的左孩子l[i]和右孩子l[i+1] 如果小于,执行此语句，让l[i]指向较大的孩子*/
        }
        if(temp>=l[i])      /*再*/
            break;
        l[s]=l[i];
        s=i;
    }
    l[s]=temp;
}

void swap(int *l,int a,int b)
{
    l[0]=l[a];
    l[a]=l[b];
    l[b]=l[0];
}

void heapsort(int *l,int lenght)
{
    int i;

/*先让数组l成为大顶堆*/
    for(i=lenght/2;i>0;i--)
    {
        heapadjust(l,i,lenght);
    }


    for(i=lenght;i>1;i--)
    {
        /*交换当前未排序的大顶堆第一个(最大的元素)和最后一个(最小的元素)*/
        swap(l,1,i);        /*注意此处是 i 而不是 lenght ，l[i]即是当前未排序的最后一个元素*/
        heapadjust(l,1,(i-1));
    }
}