树形选择排序（Tree Selection Sort）

　　树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

　　这个过程可用一棵有n个叶子结点的完全二叉树表示。例如，图表2中的二叉树表示从8个数中选出最小数的过程。8个叶子结点到根接点中的关键字，每个非终端结点中的数均等于其左右孩子结点中较小的数值，则根结点中的数即为叶子结点的最小数。在输出最小数之后，割据关系的可传递性，欲选出次小数，仅需将叶子结点中的最小数（13）改为“最大值”，然后从该叶子接点开始，和其左（或右）兄弟的数值进行比较，修改从叶子结点到根的路径上各结点的数，则根结点的数值即为最小值。同理，可依次选出从小到大的所有数。由于含有n个子结点的完全二叉树的深度为log2n+1，则在树形选择排序中，除了最小数值之外，每选择一个次小数仅需要进行log2n次比较，因此，它的时间复杂度为O(nlogn)。但是，这种排序方法尚有辅助存储空间较多、和“最大值”进行多余比较等缺点。为了弥补，威洛姆斯（J. willioms）在1964年提出了另一种形式的选择排序——堆排序。

打开IDE

创建一个工程

声名如下

#include "stdafx.h"//锦标赛排序法#include
    
     #include
     
      #include
      
       //#include
       
        #include
        
         #include
         
          using namespace std;class DataNode //胜者树结点的类定义{public:int data;//数据值int index;//树中的结点号int active;//参选标志};//锦标赛排序中的调整算法;i是表中当前//最小元素的下标,即胜者.从它开始向上调整void UpdataTree(DataNode *tree,int i){int j;if(i%2==0) //i为偶数,对手为左结点tree[(i-1)/2]=tree[i-1];//i为奇数,对手为右结点elsetree[(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
          
           =n的2的最小次幂的数{ m=(int)pow((double) 2,(double)k); if(m>=n) break;}int bottomRowSize=m;int TreeSize=2*bottomRowSize-1;//计算胜者树的大小:内结点+外结点数int loadindex=bottomRowSize-1;//外结点开始位置tree=new DataNode[TreeSize]; //动态分配胜者树结点数组空间for(i=loadindex;i
          
         
        
       
      
     
    

调用如下

//锦标赛排序法的测试void main(){cout<<"运行结果:\n";int n,b[100],i;srand(time(0));cout<<"输入待排序元素个数n:";cin>>n;for(i=0;i

运行如下

代码下载