锦标赛排序
本页面将简要介绍锦标赛排序．
定义
锦标赛排序（英文：Tournament sort），又被称为树形选择排序，是 选择排序 的优化版本，堆排序 的一种变体（均采用完全二叉树）．它在选择排序的基础上使用优先队列查找下一个该选择的元素．
引入
锦标赛排序的名字来源于单败淘汰制的竞赛形式．在这种赛制中有许多选手参与比赛，他们两两比较，胜者进入下一轮比赛．这种淘汰方式能够决定最好的选手，但是在最后一轮比赛中被淘汰的选手不一定是第二好的——他可能不如先前被淘汰的选手．
过程
以 最小锦标赛排序树 为例：
待排序元素是叶子节点显示的元素．红色边显示的是每一轮比较中较小的元素的胜出路径．显然，完成一次＂锦标赛＂可以选出一组元素中最小的那一个．
每一轮对 𝑛n
个元素进行比较后可以得到 𝑛2n2 个「优胜者」，每一对中较小的元素进入下一轮比较．如果无法凑齐一对元素，那么这个元素直接进入下一轮的比较．
完成一次「锦标赛」后需要将被选出的元素去除．直接将其设置为 ∞∞（这个操作类似 堆排序），然后再次举行「锦标赛」选出次小的元素．
之后一直重复这个操作，直至所有元素有序．
性质
稳定性
锦标赛排序是一种不稳定的排序算法．
时间复杂度
锦标赛排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 𝑂(𝑛log𝑛)O(nlogn)．它用 𝑂(𝑛)O(n) 的时间初始化「锦标赛」，然后用 𝑂(log𝑛)O(logn) 的时间从 𝑛n 个元素中选取一个元素．
空间复杂度
锦标赛排序的空间复杂度为 𝑂(𝑛)O(n)．
实现
C++Python
---|---
---|---
外部链接
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Enter-tainer, iamtwz, NachtgeistW, Tiphereth-A, Xeonacid, zhoudavinci, Alisahhh, Chihsiao, Ir1d, ksyx, mcendu, Menci, ShaoChenHeng, shawlleyw, shenshuaijie 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用