前几天写的是胜者树的构造,play()函数的实现，由于每次产生一个冠军后就把该冠军移出，所以接下来还得
继续从外部结点继续向上比赛，所以还得写一个PlayUp()函数，可每想到有这么多种情况啊，足足九种情况要
考虑，所以代码写的出奇地长，也觉得是排序中最难写的了，下面是刚写完的完整的胜者树类以及排序的实现：

大家多讨论一下这种排序吧...

#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();           //进行一趟比赛,返回每趟的冠军
    int PlayUp(int p);    //从数组e中的第p个元素开始向上重新比赛
    void WinSort();       //利用当前的胜者树进行排序
};
////////////////////////////////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];
    };
                     
    return t[0];
};
//////////////////////////////play()公有成员函数结束

////////////////////////////////////////////////////
//PlayUp() 从弹出的元素开始向上重新调整确定新的冠军
//p是刚刚作为冠军弹出的元素在e数组中的编号
//返回冠军元素的值
////////////////////////////////////////////////////
template<class T>
int WinTree<T>::PlayUp(int p)
{
    /*先进行叶子结点之间的比赛*/
    int parent;                         //存放当前结点p的父结点
    if(n%2!=0)                          //如果n是奇数
    {
        if(p<offset)                    //如果是最底层的叶子结点
        {
            int k=pow(2,h)-1+p;         //p在整个完全二叉树中的编号
            parent=(k-1)/2;
            if(p%2!=0)                  //如果p是奇数
            {
                if(e[p-1]<=e[p])
                    t[parent]=p-1;
                else
                    t[parent]=p;
            }
            else                        //如果p是偶数
            {
                if(e[p]<=e[p+1])
                    t[parent]=p;
                else
                    t[parent]=p+1;
            }
        }
        else if(p==offset)              //第一个次底层的叶子结点
        {
            parent=(n-2-1)/2;
            if(e[t[n-2]]<=e[p])
                t[parent]=t[n-2];
            else
                t[parent]=p;
        }
        else                            //次底层的叶子结点
        {
            int k=(n-1)+(p-offset);
            parent=(k-1)/2;
            if(p%2!=0)                  //如果p是奇数
            {
                if(e[p]<=e[p+1])
                    t[parent]=p;
                else
                    t[parent]=p+1;
            }
            else                        //如果p是偶数
            {
                if(e[p-1]<=e[p])
                    t[parent]=p-1;
                else
                    t[parent]=p;
            }
        }
    }
    else                                //如果n是偶数
    {
        if(p<offset)                    //如果是最底层叶子结点
        {
            int k=pow(2,h)-1+p;
            parent=(k-1)/2;
            if(p%2!=0)                  //如果p是奇数
            {
                if(e[p-1]<=e[p])
                    t[parent]=p-1;
                else
                    t[parent]=p;
            }
            else                        //如果p是偶数
            {
                if(e[p]<=e[p+1])
                    t[parent]=p;
                else
                    t[parent]=p+1;
            }
        }
        else                            //如果是次底层叶子结点
        {
            int k=(n-1)+(p-offset);
            parent=(k-1)/2;
            if(p%2!=0)                  //如果p是奇数
            {
                if(e[p-1]<=e[p])
                    t[parent]=p-1;
                else
                    t[parent]=p;
            }
            else                        //如果p是偶数
            {
                if(e[p]<=e[p+1])
                    t[parent]=p;
                else
                    t[parent]=p+1;
            }
        }
    }
    p=parent;                           //继续向上层比较
    /*如果p是最后一个内部结点,且n是奇数
    则此时p需要和次外层外部结点比赛*/
    if(p==n-2 && n%2!=0)
    {
        int k=n-2;
        parent=(k-1)/2;
        if(e[t[p]]<=e[offset])
            t[parent]=t[p];
        else
            t[parent]=offset;
        p=parent;
    };
    /*对剩下的内部结点循环向上进行比赛*/    
    while(p!=0)
    {
        parent=(p-1)/2;
        if(p%2!=0)
        {
            if(e[t[p]]<=e[t[p+1]])
                t[parent]=t[p];
            else
                t[parent]=t[p+1];
        }
        else
        {
            if(e[t[p-1]]<=e[t[p]])
                t[parent]=t[p-1];
            else
                t[parent]=t[p];
        };
        p=parent;
    };               
    return t[0];                         //返回冠军的选手号
};
////////////////////////////////////PlayUp()函数结束

////////////////////////////////////////////////////
//WinSort()公有成员函数  利用当前的胜者树进行排序
//时间复杂度是O(n*log2(n))
////////////////////////////////////////////////////
template<class T>
void WinTree<T>::WinSort()
{
    int p;                //每次移出的冠军选手号
    p=play();             //首先构造一棵胜者树,并产生第一个冠军
    for(int i=1;i<=n;i++)
    {
        cout<<e[p]<<" ";  //显示每次产生的冠军的内容
        e[t[0]]=maxValue;     //移出当前冠军选手
        p=PlayUp(p);      //进行从底层向上层的调整比赛
    };
};
///////////////////////////////////WinSort()函数结束

#endif