树形选择排序锦标赛排序cx

树形选择排序(Tree Selection Sort)，又称锦标赛排序(Tournament Sort)，是一种按锦标赛的思想进行选择排序的方法。简单选择排序花费的时间主要在比较上，每次都会进行很多重复的比较，造成浪费时间。锦标赛排序就是通过记录比较结果，减少比较次数，从而降低时间复杂度。

算法描述：

首先对n个记录的关键字进行两两比较，然后再对胜者进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树描述。

图片演示：

用锦标赛排序对下图序列排序。

两两比较构造完全二叉树。

选出最小值，并修改该叶节点关键字为∞。

重复上述过程，直至叶节点全为∞，排序完成。

性能分析：

空间复杂度：O(N)

稳定性：不稳定

缺点：辅助存储空间较多，和∞的比较多余。

为了弥补这些缺点，威洛姆斯(J·willioms)在1964年提出了另一种形式的选择排序——堆排序。

代码实现：

算法优化：

上面代码一次遍历只是找出未排序序列中的最小值，其实我们可以在遍历过程中同时找出最小值和最大值，并把每次找出的最大值按顺序放到每次排列数据的末尾。时间复杂度还是 O(N^2) ，只相对前面的减少了一半遍历次数。