在选择类排序中，除了我们以往学习过的简单选择排序和堆排序之外，比较重点的还有树形选择排序，因为这种排序在面试中也偶有出现，所以这节课我们也来讲一讲。
树形选择排序又叫锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。属于对简单选择排序的一种改进。
以数组 { 16,1,45,23,99,2,18,67,42,10 } 为例，参考图1。
图1从下向上观察，这是第一趟排序，目的是从所有数组中选出值最小的元素。我们尝试描述下具体的操作步骤。
开始两两比较，于是元素16和1比较选择1，元素45和23比较选择23，元素99和2比较选择2，18和67比较选择18，42和10比较选择10。
现在，选择出的元素1、23、2、18、10又进行两两比较，元素1和23比较选择1，元素2和18比较选择2，元素10没有比较的对象直接被选择。
现在，选择出的元素1、2、10又进行两两比较，元素1和2比较选择1，元素10没有比较的对象直接被选择。
现在，选择出的元素1、10又进行比较，选择1。最终这个1也是树形结构的树根，找个地方保存本趟排序的最小元素1。
接着，在树叶中把第一趟已经选择出的元素1标记为一个最大值 ∞（这表示元素1不可能在比较中被再次选中了），然后进行第二趟排序，如图2所示。
图2还是从下向上观察，这是第二趟排序，前面挑选出的最小值1已经找了个地方保存，这里直接把1的值修改为一个最大值∞，这样，对节点进行两两比较时，标记为最大值的节点就不可能被选中。第二趟排序需要进行什么比较呢？
开始两两比较，元素16和最大值比较，选择元素16。元素45和23、99和2、18和67、42和10就不需要再次比较（因为第一趟排序比较过了）。
现在，选择出的元素16和23比较，选择元素16。元素2和18，元素10同样因为第一趟比较过，不需要再次比较。
现在，选择出的元素16和2比较，元素10同样因为第一趟比较过，不需要再次比较。
现在，选择出的元素2、10进行比较，选择2。最终这个2也是树形结构的树根，找个地方保存本趟排序的最小元素2。
然后继续把第二趟中已经选择出的元素2标记为一个最大值，就可以开始第三趟排序，这里就不赘述了。
所以可以看到，经过一次（第一趟）的完全比较后，从第二趟开始就不再需要完全的两两比较，这样就达到了节省时间提高效率的目的，这就是树形选择排序相较于简单选择排序一个重大的改进之处。但是也应该看到，树形选择排序需要通过构造出二叉树这种树形结构来辅助排序，所以还需要辅助存储空间。
上述图1和图2意在阐述树形选择排序理论，理论上来说树形选择排序并不复杂。但若通过代码实现，则是需要构建一棵完全二叉树来实现对数据排序的。换句话说，图1和图2绘制得比较简单，很多额外的节点并没有绘制出来。
第一趟，两两比较，找到最小值保存到根节点中，如图3所示。
接着，沿着根节点向叶子节点找，找到了最小值1所在的叶子节点，把该叶子节点的值从原来保存的1修改为最大值 ∞，如图4所示。
接着要开始第二趟比较了，第二趟比较时叶子节点之间不再需要两两比较，只需要16和∞作比较，此时当然是16更小，于是，沿着这个比较路线再前进到树根，就能把当前树中的最小节点找到并保存到根中。如图5所示。
接着，沿着根节点向叶子节点找，找到了最小值2所在的叶子节点，把该叶子节点的值从原来保存的2修改为最大值 ∞，如图6所示。
持续上述步骤，就可以把整个数据序列按从小到大的顺序排列好。
下面我给出树形选择排序的实现代码。
在main主函数中，加入测试代码。
代码的执行结果如下：
此外，经过我测试，认为上述算法的实现代码是稳定的。如果你稍微调整一下其实现代码，改为不稳定的也很容易。
树形选择排序的每一趟排序都会减少需要两两比较的元素数量，从而达到了节省时间提高效率的目的，这就是树形选择排序相较于简单选择排序一个重大的改进之处。 但是我们也应该看到，树形选择排序需要通过构造出二叉树这种树形结构来辅助排序，所以还需要辅助存储空间。
请填写红包祝福语或标题
红包个数最小为10个
红包金额最低5元
醉竺
你的鼓励将是我创作的最大动力
打赏作者
抵扣说明：
1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。 2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。