找最大或者最小，蠻力算法為最優(yōu)的算法，需要比較n-1次

# 這個已經(jīng)是最優(yōu)的算法了，比較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_pivotdef 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

還有一種分治的算法，也是需要比較n-1次，類似于錦標(biāo)賽，這里比較次數(shù)就是淘汰掉的隊伍個數(shù)，劃分子問題的方法就是兩兩比較，只留最大，注意奇數(shù)的處理（直接晉級下輪）

# 兩兩比較得到最大的一半數(shù)組 def partition_max(arr):pointer = 0max_arr =[]while pointer <= len(arr)-2:max_arr += [max(arr[pointer],arr[pointer+1])]pointer +=2# 假如是奇數(shù)，加上最后一個數(shù)，偶數(shù)的話加的為空 max_arr +=arr[pointer:]return max_arr# 找最大分治的寫法，也是最優(yōu)的為比較n-1次 def findmax_recursive(arr):if len(arr) == 1:return arr[0]max_arr = partition_max(arr)return findmax_recursive(max_arr)

同時找最大和找最小，蠻力算法，找最大n-1,找最小n-2,合計2n-3

使用分組的方式比較次數(shù)：3/2 *n -2

# 找最大和最小，得到最大一半分組和最小的一半分組 def partition_max_min(arr):pointer = 0max_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 +=2max_arr +=arr[pointer:]min_arr +=arr[pointer:]return max_arr,min_arr# 這個也是最優(yōu)的算法了 def findMaxMin(arr):max_arr,min_arr = partition_max_min(arr)min = findMin(min_arr)max = findMax(max_arr)return max,min

找第二大，蠻力算法也是2n-3，采取錦標(biāo)賽的方式冠軍比較n-1次，亞軍在冠軍的手下敗將里產(chǎn)生比較logn-1次，這里需要備忘冠軍的手下敗將，但是一開始冠軍不知道，所以每個選手需要記錄他曾經(jīng)打敗過的選手

#%% class node:def __init__(self,value=None,miss=None):self.value = valueself.miss =missdef partition_max_with_nodes(arr):pointer = 0max_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# 假如是奇數(shù)，加上最后一個數(shù)，偶數(shù)的話加的為空 max_arr +=arr[pointer:]return max_arrdef 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.valuesecond_max_arr = pair.misssecond_max = findMax(second_max_arr)return first_max,second_maxarr = [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)

對于一般情況下次再研究

總結(jié)

以上是生活随笔為你收集整理的分治法：关于选择算法，找最大，找最小，同时找最大和最小，找第二大的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。