//錦標賽排序法JinBiaoSai.cpp
#include<iostream.h>
#include<iomanip.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
class DataNode //勝者樹結點的類定義
{public:
  int data;//數(shù)據(jù)值
  int index;//樹中的結點號
  int active;//參選標志
};
//錦標賽排序中的調(diào)整算法;i是表中當前
//最小元素的下標,即勝者.從它開始向上調(diào)整
void UpdataTree(DataNode *tree,int i)
{int j;
 if(i%2==0) //i為偶數(shù),對手為左結點
  tree[(i-1)/2]=tree[i-1];//i為奇數(shù),對手為右結點
 else
  tree[(i-1)/2]=tree[i+1];
 i=(i-1)/2; //i上升到雙親結點位置
 while(i)
 {if(i%2==0) j=i-1;//確定i的對手為左結點還是右結點
  else j=i+1;
  if(!tree[i].active||!tree[j].active)//比賽對手中間有一個空
   if(tree[i].active) tree[(i-1)/2]=tree[i];
   else tree[(i-1)/2]=tree[j]; //非空者上升到雙親結點
  else                         //比賽對手都不為空
   if(tree[i].data<tree[j].data) tree[(i-1)/2]=tree[i];
   else tree[(i-1)/2]=tree[j];//勝者上升到雙親結點
  i=(i-1)/2; //i上升到雙親結點
}}
//建立樹的順序存儲數(shù)組tree,將數(shù)組a[]中的元素復制到勝者樹中,
//對它們進行排序,并把結果返回數(shù)組中,n是待排序元素個數(shù)
void TournmentSort(int a[],int n)
{DataNode *tree; //勝者樹結點數(shù)組
 DataNode item;
 int m,i,j=0;
 for(int k=0;k<n;k++)//計算滿足>=n的2的最小次冪的數(shù)
  {m=pow(2,k);if(m>=n) break;}
 int bottomRowSize=m;
 int TreeSize=2*bottomRowSize-1;//計算勝者樹的大小:內(nèi)結點+外結點數(shù)
 int loadindex=bottomRowSize-1;//外結點開始位置
 tree=new DataNode[TreeSize];  //動態(tài)分配勝者樹結點數(shù)組空間
 for(i=loadindex;i<TreeSize;i++)//復制數(shù)組數(shù)據(jù)到樹的外結點中
 {tree[i].index=i;//下標
  if(j<n) {tree[i].active=1;tree[i].data=a[j++];}//復制數(shù)據(jù)
  else tree[i].active=0; //后面的結點為空的外結點
 }
 i=loadindex;           //進行初始比較尋找最小的項
 while(i)
 {j=i;
  while(j<2*i)          //處理各對比賽者
  {if(!tree[j+1].active||tree[j].data<tree[j+1].data)
    tree[(j-1)/2]=tree[j];
   else tree[(j-1)/2]=tree[j+1];//勝者送入雙親
   j+=2; //下一對參加比較的項
  }
  i=(i-1)/2;//i退到雙親,直到i=0為止
 }
 for(i=0;i<n-1;i++)//處理其他n-1個元素
 {a[i]=tree[0].data;//當前最小元素送數(shù)組a
  tree[tree[0].index].active=0;//該元素相應外結點不再比賽
  UpdataTree(tree,tree[0].index);//從該處向上修改
 }
 a[n-1]=tree[0].data;
}
//錦標賽排序法的測試
void main()
{cout<<"JinBiaoSai.cpp運行結果:\n";
 int n,b[100],i;
 srand(time(0));
 cout<<"輸入待排序元素個數(shù)n:";cin>>n;
 for(i=0;i<n;i++) b[i]=rand()%100;
 cout<<"排序前數(shù)組:\n";
 for(i=0;i<n;i++)
  cout<<setw(4)<<b[i];
 cout<<endl;
 TournmentSort(b,n);
 cout<<"排序后數(shù)組:\n";
 for(i=0;i<n;i++)
  cout<<setw(4)<<b[i];
 cout<<endl;
 cin.get();cin.get();}