排序算法之：锦标赛排序（Tournament Sort）

题目描述
锦标赛排序是一种基于选择排序思想的算法，它通过模拟体育比赛中的锦标赛机制，高效地从无序数组中找到最小（或最大）元素。该算法首先构建一个“锦标赛树”（通常用完全二叉树表示），其中每个叶子节点代表一个待排序元素，内部节点记录子节点之间的比较结果（胜者）。每次从树根取出当前最小元素后，需要重构树中从该元素对应叶子到根路径上的节点，以找出下一个最小元素。锦标赛排序适用于外部排序场景，因为它可以逐步输出有序序列而不需要将所有数据同时加载到内存。

解题过程

1. 构建初始锦标赛树

   • 将待排序数组中的每个元素作为叶子节点，按顺序排列。
   • 从叶子节点开始，两两比较相邻节点，将较小值作为父节点（胜者）。若叶子数为奇数，最后一个节点直接晋级。
   • 递归向上比较，直到生成根节点，根节点即为全局最小值。
     示例：数组 [3, 1, 4, 2] 的树结构如下（括号内为值）：

        根(1)
       /    \
     (1)    (2)
    /  \    /  \
   3    1  4    2
   

2. 输出最小值并重构树

   • 取出根节点的值（当前最小值）作为排序结果。
   • 将最小值对应的叶子节点值设为“无穷大”（表示已取出），并从该叶子节点开始向上回溯。
   • 逐层重新比较兄弟节点：若兄弟节点值较小，则更新父节点为兄弟节点的值；否则保持父节点不变。
     接上例：取出 1 后，将叶子 1 设为 ∞，重构路径：
   • 叶子 1 的兄弟节点为 3，父节点更新为 3。
   • 父节点 3 的兄弟节点为 2，根节点更新为 min(3, 2) = 2。

3. 重复步骤2直到排序完成

   • 每次重构后，根节点即为剩余元素中的最小值，重复输出和重构过程，直到所有叶子节点均为 ∞。
     接上例：后续输出顺序为 2、3、4，最终排序结果为 [1, 2, 3, 4]。

关键点与复杂度

• 时间复杂度：
  • 建树阶段需 O(n) 次比较（n 为元素数量）。
  • 每次重构需要 O(log n) 次比较（树高），共进行 n 次重构，总复杂度为 O(n log n)。
• 空间复杂度：需要 O(n) 额外空间存储二叉树结构。
• 优势：适用于流式数据（如外部排序），每次可高效获取下一个最小元素。