計算機算法-最少的比較次數同時求最大值最小值

問題描述

分别求最大值和最小值我們非常熟悉，都是通過周遊來完成的，且每種都需要n-1次比較，是以正常思維下要同時求出最大值最小值需要2(n-1)次比較，現在我們想，能不能用更少的比較次數來求出最大值和最小值呢？

我們可以先來比較數組中前兩個數字，記錄下最大值max和最小值min，此時比了1次，之後比較之後依次周遊剩下的元素兩兩一組，大的和max比，小的和min比，剩下2*（n-1）個數，互相比用掉n-1次，大的和max比用掉n-1次，小的和min比用掉n-1次，一共是3(n - 1) + 1 = 3n - 2次比較。

算法步驟

（1）判斷一下數組為奇數個還是偶數個，以便于之後的分組；

（2）定義好max，min奇數個的話直接将第一個元素賦給max，min，偶數個的話比較第一個元素和第二個元素，大的賦給max，小的賦給min；

（3）之後以步長為2周遊數組，并依次比較每個分組中元素大小，大的和max比，小的和min比，有選擇的進行替換。

代碼實作

def find_max_min(A):
    max_num = min_num = 0
    j = 0
    if len(A)%2==0:
        if A[j]<A[j+1]:
            min_num = A[j];j=j+1
            max_num = A[j];j=j+1
        else:
            max_num = A[j];j=j+1
            min_num = A[j];j=j+1
    else:
        max_num = min_num = A[j];j=j+1
    for i in range(j,len(A)-1,2):
        if A[i]>A[i+1]:
            max_num = max(A[i] , max_num)
            min_num = min(A[i+1],min_num)
        else:
            max_num = max(A[i+1] , max_num)
            min_num = min(A[i],min_num)
    return max_num,min_num

L = [52, 3, 56, 5, 2, 58, 21, 8, 90, 2,100]
print (find_max_min(L))