查找6个互异元素第二小或第二大值的最坏情况最少比较次数问题

存在更优的实现方案，最坏情况下仅需要7次比较，比现有参考实现的9次少2次，是该问题下的理论最优解。

核心逻辑 #

对于n个互异元素找第二小值的问题，最坏情况下的最优比较次数为 n + log₂n - 2，对应n=6时结果就是7次，核心思路是锦标赛排序法：

1. 先通过两两比较决出全局最小值，过程中记录所有直接输给全局最小值的元素：第二小值只可能是这些元素里的最小值，因为其他元素都输给了至少一个比全局最小值大的元素，不可能是第二小
2. 只需要在上述直接败者集合里找最小值，就能得到第二小值

6个元素的具体执行步骤 #

1. 第一轮分组比较（3次比较）：将6个元素分成3组两两比较，得到3个小组胜者，每个胜者对应记录1个直接败者
2. 第二轮胜者组比较（2次比较）：将3个小组胜者两两比较，决出全局最小值，同时把每轮输给全局最小值的元素加入它的直接败者列表
3. 败者组找最小值（最坏2次比较）：全局最小值的直接败者列表最多有3个元素，找其中最小值仅需2次比较，得到第二小值

代码实现 #

CntComparisons = 0
def isLarger(v1, v2):
    global CntComparisons
    CntComparisons += 1
    return v1 > v2

def solve(v1, v2, v3, v4, v5, v6):
    global CntComparisons
    CntComparisons = 0
    # 工具函数：比较两个元素，返回(更小的胜者, 更大的败者)
    def compare_and_return(a, b):
        if isLarger(a, b):
            return (b, a)
        return (a, b)
    
    # 第一轮分组比较：3次比较
    w1, l1 = compare_and_return(v1, v2)
    loser_map = {w1: [l1]}
    w2, l2 = compare_and_return(v3, v4)
    loser_map[w2] = [l2]
    w3, l3 = compare_and_return(v5, v6)
    loser_map[w3] = [l3]
    
    # 第二轮胜者比较：2次比较
    # 先比前两个小组胜者
    w_win1, w_lose1 = compare_and_return(w1, w2)
    loser_map[w_win1].append(w_lose1)
    # 再和第三个小组胜者比，得到全局最小值
    global_min, w_lose2 = compare_and_return(w_win1, w3)
    loser_map[global_min].append(w_lose2)
    
    # 从全局最小值的直接败者里找最小，就是第二小，最坏2次比较
    candidates = loser_map[global_min]
    second_min = candidates[0]
    for num in candidates[1:]:
        if isLarger(second_min, num):
            second_min = num
    
    print(f"#comparisons = {CntComparisons}")
    return second_min

正确性&最坏情况验证 #

• 最坏情况出现在全局最小值的直接败者有3个时，此时找败者最小值需要2次比较，总比较次数为3+2+2=7
• 所有比较均通过isLarger函数完成，没有使用值的索引、大小预判等违规操作，完全符合题目约束
• 第二小值必然是直接输给全局最小值的元素之一，逻辑严谨无遗漏

如果需要找第二大值，仅需把工具函数的逻辑反转，返回更大的作为胜者即可，比较次数完全一致。

内容的提问来源于stack exchange，提问作者JanieM