堆排序算法实现

堆用数组来实现，但是其中元素有顺序，满足最大（小）堆的性质，如a[i]>a[i+1]&&a[i]>a[i+2]，堆排序的思想是对于一个无序的数组，首先建堆，然后将第一个元素与最后一个元素交换位置，这样因为第一个元素是最大（小）值，就可以取出来了，再对其余N-1个元素进行堆得整理，代价为logn，然后再次取出第一个元素，以此类推，总的排序代价为O(N*logN)。注意建堆的代价为O(N)。

C++的实现代码如下：

/*
堆排序算法：最大时间复杂度为O(N*logN)，即每次交换到堆顶的元素都是最小的，这样堆整理的操作时间最长
堆排序与选择排序算法相似，只不过选择排序每次选出一个当前最大元素时都需要比较n-1次（n一直在递减），
即他没有记录其他元素的大小关系，这样导致每次都需要进行很多次重复比较，而堆排序则把其他元素放在堆中
堆是有序的，这样减少了每次选出最大元素的比较次数，因为其他元素的大小关系已经确定，不用再比较
*/


#include <iostream>
#include <algorithm>
using namespace std;

void heapAdjust(int *a, int i, int size);
void heapSort(int *a, int size);
void buileHeap(int *a, int size);

int main()
{
    int i, size;
    int a[100];
    while(scanf("%d", &size)==1&&size>0)
    {
        cout<<"size is "<<size<<endl;
        for(i=1;i<=size;i++)  //节点序号从1开始，方便后续的堆操作
        {
            cin>>a[i];
        }
        cout<<"input over"<<endl;
        buileHeap(a, size);
        heapSort(a, size);
        for(i=1;i<=size;i++)
            cout<<a[i]<<",";
        cout<<endl;
    }
    return 0;
}

/*调整堆的函数*/
void heapAdjust(int *a, int i, int size)
{
    int leftchild=2*i;
    int rightchild=2*i+1;
    int max=i;

    if(i<=size/2)
    {//cout<<"i="<<i<<endl;
        if(leftchild<=size&&a[leftchild]>a[max])   //注意判断leftchild和rightchild的范围是否超过了size
            max=leftchild;
        if(rightchild<=size&&a[rightchild]>a[max])
            max=rightchild;
        if(max!=i)
        {
            swap(a[i], a[max]);
            heapAdjust(a, max, size);   //只有max不等于i时才递归调用，否则会死循环
        }
    }
    return;
}

/*堆排序函数*/
void heapSort(int *a, int size)
{
    buileHeap(a, size);
    int i;
    for(i=size;i>1;i--)
    {
        swap(a[1], a[i]);  //每次把最大元素交换到最后的位置
        heapAdjust(a, 1, (i-1));   //注意此处的第三个参数应该是当前堆的长度减1
    }
    return;
}

/*建堆函数*/
void buileHeap(int *a, int size)
{
    int i;
    for(i=size/2;i>0;i--)   //非叶节点的序号最大为size/2，注意节点序号从1开始，这样方便。
    {
        heapAdjust(a, i, size);
    }
}