写了一个下午，才编写出来，觉得还是挺难写的，因为参加排序的元素的个数如果不是
2^n个，则需要构造一个完全二叉树，还是挺难的，常见的实现方法是使用两个数组，
t[n-1]和e[n],数组e存放所有的参加排序的元素，在完全二叉树中是叶子结点，t[]存放
的是比赛的阶段性胜者的编号，再进行n趟比赛排序结束，时间复杂度是O(n*log2(n))，
其实我觉得也可以只通过一个数组A[2*n-1]也可以实现，只是标号的换算有点复杂而已.
#ifndef WINNERTREE_H
#define WINNERTREE_H

#include<iostream.h>
#include<stdlib.h>
const int DS=100;
#include<cmath>

////////////////////////////////////////////////////
//WinTree<T>胜者树的类模板的定义
//参加比赛的人数n可以是任意的(不一定是2的幂方)
////////////////////////////////////////////////////
template<class T>
class WinTree
{
private:
    T* e;                 //存放参加比赛的数组元素
    int* t;               //存放胜者或者是offset之后的叶子结点
    int n;                //当前的参加比赛的人数
    int offset;           //最底层的叶子结点数
    int h;                //最大满二叉树的高度
    int maxValue;
public:
    WinTree(T* arr,int x);//构造函数
    int play();           //进行一趟比赛,返回每趟的冠军
};
////////////////////////////////WinTree<T>类模板结束

////////////////////////////////////////////////////
//带参数的构造函数
//通过数组来对当前的胜者树进行初始化
//arr数组中是参加比赛的元素,x是参加比赛的人数
////////////////////////////////////////////////////
template<class T>
WinTree<T>::WinTree(T* arr,int x)
{
    /*初始化相关参数*/
    n=x;                            //参加比赛的人数
    e=new T[x];                     //开辟比赛选手的数组
    t=new int[x-1];                 //存放胜者的选手号的数组
    for(int i=0;i<x;i++)            //初始化选手数组
        e[i]=arr[i];
    maxValue=10000;

    /*首先根据参加比赛的选手数n求出最
    底曾叶子结点数和次底层叶子结点数*/
    h=int(log(2*n-1)/log(2));       //最大满二叉树的深度
    offset=int(2*n-1-(pow(2,h)-1)); //计算最底层的叶子结点数
};
////////////////////////////////////带参数的构造函数

////////////////////////////////////////////////////
//play()公有成员函数  对所有的选手进行一次比赛
////////////////////////////////////////////////////
template<class T>
int WinTree<T>::play()
{
    /*首先让最底层的叶子结点进行比赛*/
    int parent;                          //存放胜者的父结点地址
    for(int i=0;i<offset;i+=2)
    {
        parent=int((pow(2,h)-1+i)/2);    //先计算父结点地址
        if(e[i]<=e[i+1])                 //如果e[i]胜者
            t[parent]=i;                 //把胜者放入t数组父结点位置
        else                             //如果e[i+1]是胜者
            t[parent]=i+1;
    };
    
    /*让次外层上的叶子结点进行比赛*/
    int p=offset;                        //处理次底层叶子的游标
   
    if(n%2!=0)                           //如果参赛人数是奇数
    {                                    //让次外层第一个叶子结点和
        if(e[t[parent]]<=e[p])             //前一个内部结点进行比赛
            t[(parent-1)/2]=t[parent];   //把胜者存入t中
        else
            t[(parent-1)/2]=p;
        p=p+1;
    };

    /*处理剩下的次外层上的叶子结点*/
    for(;p<n;p+=2)
    {
        int k=int(pow(2,h)-1-n+p);       //计算当前叶子结点p在当前二叉树中编号
        parent=int((k-1)/2);             //计算父结点在t中的地址
        if(e[p]<=e[p+1])                 //把胜者放入到t数组中的父结点位置
            t[parent]=p;
        else
            t[parent]=p+1;
    };

    /*对t中剩下的元素进行继续向上比赛*/
    if(n%2!=0)                           //如果n是奇数,说明已经有一个与叶
        p=n-3;                           //子结点比赛了,p从t中倒数第二个元素开始
    else
        p=n-2;                           //p从t中的倒数第一个元素开始向前比赛

    for(;p>0;p-=2)
    {                                    //p始终指向左子树
        parent=int((p-1)/2);
        if(e[t[p]]>=e[t[p-1]])           
            t[parent]=t[p-1];            //存放胜者的编号
        else
            t[parent]=t[p];
    };

    T temp=e[t[0]];                     
    e[t[0]]=maxValue;                    //移出当前冠军选手
    return temp;                         //返回胜者的选手
};
//////////////////////////////play()公有成员函数结束

#endif
#include"WinnerTree.h"
#include<iostream.h>

////////////////////////////////////////////////////
//WinSort()全局函数 通过胜者树实现的排序
////////////////////////////////////////////////////
template<class T>
void WinSort(T* Vector,int n)
{
    WinTree<T> WT(Vector,n);       //构造一棵胜者树
    for(int i=0;i<n;i++)
        Vector[i]=WT.play();       //进行n趟排序
};
///////////////////////////////////WinSort()函数结束

////////////////////////////////////////////////////
//main()函数   测试胜者树的排序方法
//该算法的时间复杂度是O(n*log2(n))
////////////////////////////////////////////////////
int main()
{
    int a[7]={21,25,49,25,16,8,63};
    WinSort(a,7);

    for(int i=0;i<7;i++)
        cout<<a[i]<<" ";

    return 0;
};
//////////////////////////////////////main()函数结束

[[it] 本帖最后由 geninsf009 于 2009-2-17 19:48 编辑 [/it]]