heapsort.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>                  //堆排序

const int N=8;
void output(int table[],int n);        //输出数组的N个元素，略
void swap(int table[],int i,int j);    //交换table[i]、table[j]的值，略

void sift(int table[],int left,int right)
{                                      //将以第left个元素为根结点的子树调整成堆
    int i,j,x;
    i=left;
    j=2*i;                             //第j个元素是第i个元素的左孩子
    x=table[i];                        //获得第i个元素的值
    while(j<=right)
    {
        if(j<right && table[j]>table[j+1])
            j++;                       //如果右孩子值较小时,j表示右孩子
        if(x>table[j])                 //第i个元素值较大
        {
            table[i]=table[j];         //设置第i个元素为j的值
            i=j;                       //i、j向下滑动一层
            j=2*i;
        }
        else
            j=right+1;
    }
    table[i]=x;
    cout<<"sift  "<<left<<"~"<<right<<"  ";
    output(table,N+1);
}

void heapsort(int table[],int n)
{
    int j;
    for(j=n/2;j>0;j--)                 //建堆
        sift(table,j,n);
    for(j=n;j>1;j--)                   //调整成堆
    {
        swap(table,1,j);               //根(最小)值交换到后面
        sift(table,1,j-1);
    }
}

void main()
{
    int a[N+1]={0,5,3,7,4,6,8,2,1};
    cout<<"N="<<N;
    output(a,N+1);
    heapsort(a,N);
}

/*
程序运行结果如下：
N=8 table:  0 5 3 7 4 6 8 2 1 
sift  4~8   table:  0 5 3 7 1 6 8 2 4 
sift  3~8   table:  0 5 3 2 1 6 8 7 4 
sift  2~8   table:  0 5 1 2 3 6 8 7 4 
sift  1~8   table:  0 1 3 2 4 6 8 7 5 
sift  1~7   table:  0 2 3 5 4 6 8 7 1 
sift  1~6   table:  0 3 4 5 7 6 8 2 1 
sift  1~5   table:  0 4 6 5 7 8 3 2 1 
sift  1~4   table:  0 5 6 8 7 4 3 2 1 
sift  1~3   table:  0 6 7 8 5 4 3 2 1 
sift  1~2   table:  0 7 8 6 5 4 3 2 1 
sift  1~1   table:  0 8 7 6 5 4 3 2 1 
*/

void output(int table[],int n)         //输出数组的N个元素
{
    cout<<" table:  ";
    for(int i=0;i<n;i++)
        cout<<table[i]<<" ";
    cout<<endl;
}

void swap(int table[],int i,int j)     //交换table[i]、table[j]的值
{                        
    int temp=table[i];
    table[i]=table[j];
    table[j]=temp;
}