经典排序之堆排序

1.堆

  堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：

  Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

  即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

  堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键 字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

2.堆排序的思想

   利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

    其基本思想为(大顶堆)：

    1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；

    2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]; 

    3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最 后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排 序过程完成。

    操作过程如下：

     1)初始化堆：将R[1..n]构造为堆；

     2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

    因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

以下C代码为当堆为2叉堆时，先构建一个大堆，然后每次把堆顶元素放置当前数组的最后位置得到一个从小到大的数组序列

#include <stdio.h>
#define leftChild(i) (2*(i)+1)
void swap(int *a,int *b)
{
    int tem;
    tem = *a;
    *a = *b;
    *b = tem;
}
void HashJust(int *a,int i,int length)//调整堆
{
    int child;
    int tem;
    for(tem = a[i];leftChild(i)<length;i=child)
    {
        child = leftChild(i);
        if(child<length-1&&a[child+1]>a[child])//找到孩子节点中较大的元素
        child++;
        if(tem<a[child])//如果父节点小于最大的孩子节点，那么就交换该节点。
        a[i] = a[child];
        else break;
    }
    a[i] = tem;
}
void HashSort(int *a,int length)
{
    int i;
    for(i = length/2;i>=0;i--)//从最后一个非叶节点开始向下调整使其成为一个最大堆
    HashJust(a,i,length);
    for(i = length-1;i>0;i--)
    {
        swap(&a[0],&a[i]);//将大堆堆顶元素放置数组的最后位置
        HashJust(a,0,i);//每次调整时只调整当前堆的大小，从堆顶0开始向下调整
    }
}
int main()
{
    int a[] = {1,4,9,2,3,5,7,8,6};
    int size;
    int i;
    size = sizeof(a)/sizeof(int);
    HashSort(a,size);
    for(i = 0; i < size; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

小注：在C语言中没有引用，所有在交换两个元素时，不能够用传引用的方法进行，因此这里借助于传地址方法交换两个数。