从上述可见，选择排序主要进行关键字之间的比较，因此改进简单选择排序应从如何减少比较次数出发考虑。显然从 n 个关键字中选出最小值，至少需要 n-1 次比较，然而，继续在剩下的 n-1 个关键字中选择次小关键字就并非一定要进行 n-2 次比较，若能利用前 n 次比较所得信息，则可减少以后每趟的比较次数。锦标赛便是一种选择排序。例如，8个运动员决出前三名至多需要 11 场比赛，而不是 7+6+5=18 场比赛(它的前提就是，若乙胜丙，甲胜乙，则甲定胜丙)，亚军只能产生于分别在决赛和半决赛和第一轮比赛中输给冠军的选手，这就是树形选择排序。
树形选择排序，又称为锦标赛排序，是一种按照锦标赛思想进行选择排序的方法。首先对 n 个记录的关键字进行两两比较，然后在剩下的 (n+1)/2 个记录中再进行两两比较，如此重复，直至选出最小关键字为止(选冠军)。输出最小关键字，然后把最小关键字置为_MAX_(MAX_INT)，然后又重新从这 n 个记录中选择最小的，此时的最小即次小，如此重复，直到输出所有关键字。代码如下：
[cpp] view plaincopy
/*
* 对树进行筛选：从叶子节点开始，两两一起选出最小的，作为双亲
*/
static void AdjustTree(int *Tree,int length,int high){
/*调整至根节点，结束调整*/
if(length==1){
return;
}
else{
int nextlength=(length+1)/2;
int adjustpos=high-length+1-nextlength;
/*选择两个叶子，选择其中较小的作为两个叶子的双亲*/
for(int i=high-length+1;iTree[i+1]) ){
Tree[adjustpos]=Tree[i+1];
}
else{
Tree[adjustpos]=Tree[i];
}
adjustpos++;
}
AdjustTree(Tree,nextlength,high-length);
}
}
/*
* 根据最底层节点个数n，返回整棵树的节点数
*/
static int GetTreeSize(int n){
if(n==1){
return 1;
}
else{
return (n+GetTreeSize((n+1)/2));
}
}
/*
* 对sq+1,sq+2,sq+3,...,sq+length 进行树形选择排序
*/
void TreeSelectSort(int *sq,int length){
/*根据叶子节点数为length，创建一个二叉树，用顺序存储结构表示*/
/* 7个叶子，需要节点数为 7+4+2+1=14
O
/ \
O O
/\ / \
O O O O
/\ /\ /\ /
O OO O O OO
*/
/*Tree指向这个二叉树的指针，TreeSize保存二叉树的节点总数*/
int TreeSize=0;
int *Tree=NULL;
TreeSize=GetTreeSize(length);
//printf("\nTreeSize=%d\n",TreeSize);
Tree=(int *)malloc(TreeSize*sizeof(int));
if(Tree!=NULL){
memset(Tree,0,TreeSize*sizeof(int));
//复制序列到树结构中
for(int i=TreeSize-length,j=1;i
*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。
发布文章
