分治法：关于选择算法，找最大，找最小，同时找最大和最小，找第二大_找第二大 最少比较次数

找最大或者最小，蛮力算法为最优的算法，需要比较n-1次

# 这个已经是最优的算法了，比较n-1次
def findMax(arr):
    max_pivot = arr[0]
    
    for i in range(1,len(arr)):
        if arr[i] > max_pivot:
            max_pivot = arr[i]
    
    return max_pivot

def findMin(arr):
    min_pivot = arr[0]
    
    for i in range(1,len(arr)):
        if arr[i] < min_pivot:
            min_pivot = arr[i]
    
    return min_pivot
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

还有一种分治的算法，也是需要比较n-1次，类似于锦标赛，这里比较次数就是淘汰掉的队伍个数，划分子问题的方法就是两两比较，只留最大，注意奇数的处理（直接晋级下轮）

# 两两比较得到最大的一半数组
def partition_max(arr):
    
    pointer = 0
    max_arr =[]
    
    while pointer <= len(arr)-2:
        max_arr += [max(arr[pointer],arr[pointer+1])]
        pointer +=2
    # 假如是奇数，加上最后一个数，偶数的话加的为空   
    max_arr +=arr[pointer:]
    
    return max_arr

# 找最大分治的写法，也是最优的为比较n-1次
def findmax_recursive(arr):
    if len(arr) == 1:
        return arr[0]
    
    max_arr = partition_max(arr)
    return findmax_recursive(max_arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

同时找最大和找最小，蛮力算法，找最大n-1,找最小n-2,合计2n-3

使用分组的方式比较次数：3/2 *n -2

# 找最大和最小，得到最大一半分组和最小的一半分组
def partition_max_min(arr):
    
    pointer = 0
    max_arr =[]
    min_arr =[]
    
    while pointer <= len(arr)-2:
        if arr[pointer] >=arr[pointer+1]:
            max_arr.append(arr[pointer])
            min_arr.append(arr[pointer+1])
        else:
            max_arr.append(arr[pointer+1])
            min_arr.append(arr[pointer])
            
        pointer +=2
        
    max_arr +=arr[pointer:]
    min_arr +=arr[pointer:]
    
    return max_arr,min_arr

# 这个也是最优的算法了
def findMaxMin(arr):
    max_arr,min_arr = partition_max_min(arr)
    min = findMin(min_arr)
    max = findMax(max_arr)
    
    return max,min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

找第二大，蛮力算法也是2n-3，采取锦标赛的方式冠军比较n-1次，亚军在冠军的手下败将里产生比较logn-1次，这里需要备忘冠军的手下败将，但是一开始冠军不知道，所以每个选手需要记录他曾经打败过的选手

#%%
class node:
    def __init__(self,value=None,miss=None):
        self.value = value
        self.miss =miss
    
def partition_max_with_nodes(arr):
    
    pointer = 0
    max_arr =[]
    
    while pointer <= len(arr)-2:
        if arr[pointer].value >=arr[pointer+1].value:
            
            arr[pointer].miss.append(arr[pointer+1].value)
            max_arr.append(arr[pointer])
        else:
            arr[pointer+1].miss.append(arr[pointer].value)
            max_arr.append(arr[pointer+1])
            
        pointer +=2
    # 假如是奇数，加上最后一个数，偶数的话加的为空   
    max_arr +=arr[pointer:]
    
    return max_arr
    
def findMaxSecondmax(arr):
    arr_node =[]
    for i in range(len(arr)):
        arr_node.append(node(arr[i],[]))
        
    def findmax_recursive(arr):
        if len(arr) == 1:
            return arr[0]
        
        max_arr = partition_max_with_nodes(arr)
        return findmax_recursive(max_arr)
    
    pair = findmax_recursive(arr_node)
    
    first_max = pair.value
    second_max_arr = pair.miss
    
    second_max = findMax(second_max_arr)
    return first_max,second_max
        

arr = [4,44,5,77,8,32,18,99,377,55,33,11,12,999,678]
print(arr)
##print(findMax(arr))
##print(partition_max(arr))
##print(findmax_recursive(arr))
#print(partition_max_min(arr))
#print(findMaxMin(arr))
print(findMaxSecondmax(arr))

[4, 44, 5, 77, 8, 32, 18, 99, 377, 55, 33, 11, 12, 999, 678]
(999, 678)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

对于一般情况下次再研究