51｜树形选择排序：按照锦标赛的思想进行排序
王健伟
你好，我是王健伟。
在选择类排序中，除了我们以往学习过的简单选择排序和堆排序之外，比较重点的还有树形选择排序，因为这种排序在面试中也偶有出现，所以这节课我们也来讲一讲。
基本概念与算法描述
树形选择排序又叫锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。属于对简单选择排序的一种改进。
我们尝试描述一下树形选择排序算法：对 n 个记录的关键字进行两两比较。然后在其中 ⌈⌉ 个较小者中再进行两两比较，如此重复，直到选出最小关键字（按从小到大排序）为止。
以数组 { 16,1,45,23,99,2,18,67,42,10 } 为例，参考图 1。
图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。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
树形选择排序是一种基于锦标赛思想的选择排序方法，通过构建完全二叉树来辅助排序，从而提高效率。文章详细阐述了树形选择排序的原理和实现过程，包括实现代码和时间复杂度、空间复杂度的分析。树形选择排序的时间复杂度为O(nlog2n)，空间复杂度为O(n)，并且是稳定的。该算法通过多趟排序逐步选出最小关键字，减少了需要两两比较的元素数量，节省时间提高效率。此外，文章还留下了思考题，引发读者深入思考。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论