樹(shù)形選擇排序(tree selection sort)是堆排序的一個(gè)過(guò)渡，并不是核心算法，大家可以結(jié)合介紹和C++代碼的范例進(jìn)行理解。

（1）算法介紹

樹(shù)形選擇排序(Tree Selection Sort)，又稱錦標(biāo)賽排序(Tournament Sort)，是一種按錦標(biāo)賽的思想進(jìn)行選擇排序的方法。簡(jiǎn)單選擇排序花費(fèi)的時(shí)間主要在比較上，每次都會(huì)進(jìn)行很多重復(fù)的比較，造成浪費(fèi)時(shí)間。錦標(biāo)賽排序就是通過(guò)記錄比較結(jié)果，減少比較次數(shù)，從而降低時(shí)間復(fù)雜度。

（2）算法描述

首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后再對(duì)勝者進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄為止。這個(gè)過(guò)程可用一棵有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)描述。

（3）算法分析

1. 時(shí)間復(fù)雜度：O(NlogN)

2. 空間復(fù)雜度：O(N)

3. 穩(wěn)定性：穩(wěn)定(依賴于具體實(shí)現(xiàn))

4. 缺點(diǎn)：輔助存儲(chǔ)空間較多，和∞的比較多余。

為了彌補(bǔ)這些缺點(diǎn)，威洛姆斯(J·willioms)在1964年提出了另一種形式的選擇排序——堆排序。

（4）標(biāo)準(zhǔn)錦標(biāo)賽排序原理：

對(duì)N個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，選出最?。ù螅┑膎/2個(gè)數(shù)，再進(jìn)行新一輪的比較，直到選出最?。ù螅┑摹?/p>

1. 把N個(gè)數(shù)放到完全二叉樹(shù)的葉子節(jié)點(diǎn)，兩兩比較，選出最小的作為根節(jié)點(diǎn)，且保存到數(shù)組中

2. 把最小的原始值設(shè)為無(wú)窮大，從那個(gè)地方開(kāi)始新一輪比較

注：第一次比較n-1，后面都是log2(n)次

（5）C++代碼實(shí)現(xiàn)如下：

/*
 * 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;

/*樹(shù)的結(jié)構(gòu)*/
struct BinaryTreeNode{
	bool from; //推斷來(lái)源, 左true, 右false
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};

/*構(gòu)建葉子節(jié)點(diǎn)*/
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;
}

/*不足偶數(shù)時(shí), 需補(bǔ)充節(jié)點(diǎn)*/
BinaryTreeNode* addMaxNode (BinaryTreeNode* list, int n)
{
	/*最大節(jié)點(diǎn)*/
	BinaryTreeNode* maxNode = new BinaryTreeNode(); //最大節(jié)點(diǎn), 用于填充
	maxNode->from = true;
	maxNode->m_nValue = INT_MAX;
	maxNode->m_pLeft = NULL;
	maxNode->m_pRight = NULL;

	/*復(fù)制數(shù)組*/
	BinaryTreeNode* childNodes = new BinaryTreeNode[n+1]; //添加一個(gè)節(jié)點(diǎn)
	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;
}

/*依據(jù)左右子樹(shù)大小, 創(chuàng)建樹(shù)*/
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);

}

/*返回樹(shù)根, 又一次計(jì)算數(shù)*/
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;
}

/*從上到下打印樹(shù)*/
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;
}

如果我們編譯并運(yùn)行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

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