树形选择排序(tree selection sort)是堆排序的一个过渡，并不是核心算法，大家可以结合介绍和C++代码的范例进行理解。
（1）算法介绍
树形选择排序(Tree Selection Sort)，又称锦标赛排序(Tournament Sort)，是一种按锦标赛的思想进行选择排序的方法。简单选择排序花费的时间主要在比较上，每次都会进行很多重复的比较，造成浪费时间。锦标赛排序就是通过记录比较结果，减少比较次数，从而降低时间复杂度。
（2）算法描述
首先对n个记录的关键字进行两两比较，然后再对胜者进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树描述。
（3）算法分析
1. 时间复杂度：O(NlogN)
2. 空间复杂度：O(N)
3. 稳定性：稳定(依赖于具体实现)
4. 缺点：辅助存储空间较多，和∞的比较多余。
为了弥补这些缺点，威洛姆斯(J·willioms)在1964年提出了另一种形式的选择排序——堆排序。
（4）标准锦标赛排序原理：
对N个记录的关键字进行两两比较，选出最小（大）的n/2个数，再进行新一轮的比较，直到选出最小（大）的。
1. 把N个数放到完全二叉树的叶子节点，两两比较，选出最小的作为根节点，且保存到数组中
2. 把最小的原始值设为无穷大，从那个地方开始新一轮比较
注：第一次比较n-1，后面都是log2(n)次
（5）C++代码实现如下：
/*
* TreeSelectionSort.cpp
*
* Created on: 2014.6.11
* Author: Spike
*/
/*eclipse cdt, gcc 4.8.1*/
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <climits>
using namespace std;
/*树的结构*/
struct BinaryTreeNode{
bool from; //推断来源, 左true, 右false
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
/*构建叶子节点*/
BinaryTreeNode* buildList (const std::vector<int>& L)
{
BinaryTreeNode* btnList = new BinaryTreeNode[L.size()];
for (std::size_t i=0; i<L.size(); ++i)
{
btnList[i].from = true;
btnList[i].m_nValue = L[i];
btnList[i].m_pLeft = NULL;
btnList[i].m_pRight = NULL;
}
return btnList;
}
/*不足偶数时, 需补充节点*/
BinaryTreeNode* addMaxNode (BinaryTreeNode* list, int n)
{
/*最大节点*/
BinaryTreeNode* maxNode = new BinaryTreeNode(); //最大节点, 用于填充
maxNode->from = true;
maxNode->m_nValue = INT_MAX;
maxNode->m_pLeft = NULL;
maxNode->m_pRight = NULL;
/*复制数组*/
BinaryTreeNode* childNodes = new BinaryTreeNode[n+1]; //添加一个节点
for (int i=0; i<n; ++i) {
childNodes[i].from = list[i].from;
childNodes[i].m_nValue = list[i].m_nValue;
childNodes[i].m_pLeft = list[i].m_pLeft;
childNodes[i].m_pRight = list[i].m_pRight;
}
childNodes[n] = *maxNode;
delete[] list;
list = NULL;
return childNodes;
}
/*依据左右子树大小, 创建树*/
BinaryTreeNode* buildTree (BinaryTreeNode* childNodes, int n)
{
if (n == 1) {
return childNodes;
}
if (n%2 == 1) {
childNodes = addMaxNode(childNodes, n);
}
int num = n/2 + n%2;
BinaryTreeNode* btnList = new BinaryTreeNode[num];
for (int i=0; i<num; ++i) {
btnList[i].m_pLeft = &childNodes[2*i];
btnList[i].m_pRight = &childNodes[2*i+1];
bool less = btnList[i].m_pLeft->m_nValue <= btnList[i].m_pRight->m_nValue;
btnList[i].from = less;
btnList[i].m_nValue = less ?
btnList[i].m_pLeft->m_nValue : btnList[i].m_pRight->m_nValue;
}
buildTree(btnList, num);
}
/*返回树根, 又一次计算数*/
int rebuildTree (BinaryTreeNode* tree)
{
int result = tree[0].m_nValue;
std::stack<BinaryTreeNode*> nodes;
BinaryTreeNode* node = &tree[0];
nodes.push(node);
while (node->m_pLeft != NULL) {
node = node->from ? node->m_pLeft : node->m_pRight;
nodes.push(node);
}
node->m_nValue = INT_MAX;
nodes.pop();
while (!nodes.empty())
{
node = nodes.top();
nodes.pop();
bool less = node->m_pLeft->m_nValue <= node->m_pRight->m_nValue;
node->from = less;
node->m_nValue = less ?
node->m_pLeft->m_nValue : node->m_pRight->m_nValue;
}
return result;
}
/*从上到下打印树*/
void printTree (BinaryTreeNode* tree) {
BinaryTreeNode* node = &tree[0];
std::queue<BinaryTreeNode*> temp1;
std::queue<BinaryTreeNode*> temp2;
temp1.push(node);
while (!temp1.empty())
{
node = temp1.front();
if (node->m_pLeft != NULL && node->m_pRight != NULL) {
temp2.push(node->m_pLeft);
temp2.push(node->m_pRight);
}
temp1.pop();
if (node->m_nValue == INT_MAX) {
std::cout << "MAX" << " ";
} else {
std::cout << node->m_nValue << " ";
}
if (temp1.empty())
{
std::cout << std::endl;
temp1 = temp2;
std::queue<BinaryTreeNode*> empty;
std::swap(temp2, empty);
}
}
}
int main ()
{
std::vector<int> L = {49, 38, 65, 97, 76, 13, 27, 49};
BinaryTreeNode* tree = buildTree(buildList(L), L.size());
std::cout << "Begin : " << std::endl;
printTree(tree); std::cout << std::endl;
std::vector<int> result;
for (std::size_t i=0; i<L.size(); ++i)
{
int value = rebuildTree (tree);
std::cout << "Round[" << i+1 << "] : " << std::endl;
printTree(tree); std::cout << std::endl;
result.push_back(value);
}
std::cout << "result : ";
for (std::size_t i=0; i<L.size(); ++i) {
std::cout << result[i] << " ";
}
std::cout << std::endl;
return 0;
}如果我们编译并运行上述程序，那么它应该产生以下结果：
Begin : 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49 Round[1] : 27 38 27 38 65 76 27 49 38 65 97 76 MAX 27 49 Round[2] : 38 38 49 38 65 76 49 49 38 65 97 76 MAX MAX 49 Round[3] : 49 49 49 49 65 76 49 49 MAX 65 97 76 MAX MAX 49 Round[4] : 49 65 49 MAX 65 76 49 MAX MAX 65 97 76 MAX MAX 49 Round[5] : 65 65 76 MAX 65 76 MAX MAX MAX 65 97 76 MAX MAX MAX Round[6] : 76 97 76 MAX 97 76 MAX MAX MAX MAX 97 76 MAX MAX MAX Round[7] : 97 97 MAX MAX 97 MAX MAX MAX MAX MAX 97 MAX MAX MAX MAX Round[8] : MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX result : 13 27 38 49 49 65 76 97
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程