树形选择排序又称锦标赛排序; 比如,在8个运动员中决出前3名至多需要11场比赛, 而不是7+6+5=18场比赛(它的前提是甲胜乙，乙胜丙，则甲必能胜丙)
首先对n个记录的关键字进行两两比较，然后在(n/2)个较小者之间再进行两两比较，直至选出最小关键字的记录为止，这个过程可用一颗有n个叶子结点的完全二叉树表示。关于完全二叉树的定义和与本排序算法用到的性质见附录1
示意图
算法分析
由于含n个叶子结点的完全二叉树的深度为[log2n]+1, 则在树形选择排序中，除了最小关键字外，每选择一个次小关键字仅需进行log2n次比较，因此它的时间复杂度为nlogn.。但是它需要的辅助空间为2*n-1。而且它在选择过程中，和"最大值"进行了多余的比较。 另外，该算法是不稳定的。
代码实现
运行
附录1 完全二叉树
定义：设二叉树深度为h，除第h层外，其他各层(1 ~ h-1)的结点数都达到最大个数，第h层所有的结点都集中在最左边，这就是完全二叉树。
性质：
1] 结点i (i>1)的双亲结点为i/2
2] 结点i的左孩子结点为2*i， 右孩子结点为2*i+1
3] 叶子结点数n0, 度为2(有左、右孩子结点)的结点数n2， 则n0 = n2+1
性质3]证明：
设n1为二叉树中度为1的结点数。因为二叉树中所有结点数的度均不大于2。所以二叉树的结点数n = n0 + n1 +n2 -- (1)。
又除根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点射出的，所以又有B=n1+2*n2，于是得n = B+1 = n1+2*n2+1 – (2)。
THE END