锦标赛排序学习笔记

c_legg · 2025-02-04 19:16:48 · 算法·理论

前言

本来也不用写的，是碰到排序题发现根本不会快排才学了一下锦标赛排序的啊。

介绍

锦标赛排序可以用这个等式来描述：

就是这样的，锦标赛排序本质上就是维护一个小根堆（锦标赛排序树），每次取走最小值，而且较堆排序更易于实现。

实现

首先，设原数组为 a，锦标赛排序树为 \text{tr}，还有一棵树 \text{id}，排序完的数组为 b。

这里我们用数组存储树，所以 \text{tr} 和 \text{id} 也是数组，其中对于所有整数 i\in[1,n]，都有 \text{tr}_{i+n-1}=a_i,id_{i+n-1}=i。也就是说，\text{tr} 的第 n 层的元素全等于 a 中的所有元素。

在 \text{tr} 中，任意两个兄弟节点的父节点是他们的最小值，所以在开始时，\text{tr}_1=\min{a}，同时可以发现：对于所有整数 i\in[1,2n-1]，\text{tr}_i\in a，可以发现，此时锦标赛排序树满足小根堆的性质，大致长这样（图片来自 oi-wiki）：

可以理解为有 n 个人在打淘汰赛，经过 \log n 场比赛后就会产生出冠军，上图中黑线表示被淘汰。

根据选择排序的规则，我们找到了 a 的最小值后，就应当删掉它去找次小值，在锦标赛排序中也一样。我们要找到最小值的位置，然后把最小值改成 \infty，此时可以像堆一样进行向上调整，调整后的树是这样的：

也就是说，我们在 \Theta(\log n) 的时间里，就找到了次小数！以此类推，最坏情况下完成排序的时间复杂度为 \Theta(n\log n)。

但这个时候有个问题，我们怎么确定最小值的位置？我们可以用另一棵树 \text{id}，它标记了锦标赛排序树上每个节点在 a 中的位置，用上面的图举个例子，我们用下标表示 \text{id}：

大家现在都懂了吧？让我们放代码：

复杂度分析

上面已经提到过了：锦标赛排序的时间复杂度最好和最坏均为 \Theta(n\log n)+\Theta(n)，显然优于归并排序。空间复杂度为 \Theta(n)，常数为 5。

参考文献（撒花）

锦标赛排序 - OI Wiki

树形选择排序(锦标赛排序)_锦标赛排序是稳定的排序方法吗-CSDN博客