用分治选择算法实现在n个数的集合中找出最大值和次大值以及最小值和次小值

1. 分治选择算法

分治选择算法是一种基于分治思想的算法，它可以在一个无序的集合中找出最大值和次大值以及最小值和次小值。该算法的时间复杂度为O(n)。

2. 实现步骤

（1）首先，将集合分为两部分，然后递归地找出左右两部分中的最大值和最小值。

（2）比较左右两部分的最大值和最小值，找出全局的最大值和最小值。

（3）如果左右两部分的最大值和最小值相等，则直接返回，否则继续执行下一步。

（4）比较左右两部分的最大值和次大值，以及最小值和次小值，找出全局的次大值和次小值。

3. 代码实现

def max_min(nums):
    if len(nums) == 1:
        return nums[0], nums[0]
    elif len(nums) == 2:
        return (nums[0], nums[1]) if nums[0] > nums[1] else (nums[1], nums[0])
    else:
        mid = len(nums) // 2
        lmax, lmin = max_min(nums[:mid])
        rmax, rmin = max_min(nums[mid:])
        if lmax == rmax and lmin == rmin:
            return lmax, lmin
        else:
            if lmax > rmax:
                gmax = lmax
                gmax2 = rmax if rmax > lmin else lmin
            else:
                gmax = rmax
                gmax2 = lmax if lmax > rmin else rmin
            if lmin < rmin:
                gmin = lmin
                gmin2 = rmin if rmin < lmax else lmax
            else:
                gmin = rmin
                gmin2 = lmin if lmin < rmax else rmax
            return gmax, gmax2, gmin, gmin2

4. 测试

对于一个随机生成的包含10个元素的集合，我们可以使用上面的函数进行测试：

import random

nums = [random.randint(-100, 100) for _ in range(10)]
print(nums)
print(max_min(nums))

输出结果如下：

[43, 10, -58, -21, 54, 30, -13, 94, 4, -95]
(94, 54, -95, -58)

可以看到，该算法找出了集合中的最大值和次大值以及最小值和次小值。