第1讲. 打擂台思想

打擂台主要用于解决最值问题，选择排序就应用了该思想。

1. 打擂台模型

- 擂主初始化

- 循环攻擂

◆注意：擂主初始化最好是真实元素，若初始化值是虚构的一定要根据情况虚构好，不然会影响结果； 攻擂时不能遗漏元素，若擂主初始化为真实元素，该元素不需要再来攻擂。

2. 求最大值

列表 a 存放着一些不重复整数，求 a 中的最大值

实现代码 1：擂主初始化为真实元素

max = a[0] # a[0]是真实元素
for i in range(1,len(a)): # 循环攻擂,a[0]不需要攻擂
     if a[i]>max:
         max = a[i]
print('最大值为：',max)

实现代码 2：擂主初始化为虚构元素

max = -2**31 # -2**31 是虚构的一个很小的数
for i in range(len(a)): # 循环攻擂，每个元素都要攻擂
     if a[i]>max:
         max = a[i]
print('最大值为：',max)

3. 最大值的位置

列表 a 存放着一些不重复整数，求 a 中的最大值在 a 中的索引位置

max = 0
for i in range(1,len(a)):
     if a[i]>a[max]:
         max = i
print('最大值的位置和值分别为：',max,a[max])

4. 条件擂台

列表 a 存放着一些不重复整数，求 a 中的最大偶数的位置

max = -1 # 虚构擂主 -1 是虚构值
for i in range(len(a)):
     if a[i]%2==0 and (max==-1 or a[i]>a[max]):
         max = i
if max==-1:
     print('列表 a 中无偶数')
else:
     print('最大偶数的位置和值分别为：',max,a[max])

5. 选择排序：不断减少未定区间的排序思想

列表 a 中存放着一些整数元素，编程实现列表 a 中的元素按升序排列。 在未定区间内确定一个元素，未定区间减少一个元素。直到未定区间剩 1 个元素或 0 个元素。 选择排序在未定区间确定元素的方法：在未定区间找出最小数的位置，与未定区间开始位置进行交换。

（1）先找位置再交换

n = len(a)
for i in range(n-1):
     #未定区间[i, n-1]
     k = i 
     for j in range(i+1,n):
         if a[j]<a[k]: 
             k = j
     if k!=i:
         a[i],a[k]=a[k],a[i]

一道高考题

n = len(a)
for i in range(n-1):
    k = n-1
    for j in range(i,n-1):
        if a[j]<a[k]: 
            k = j
    if k!=i:
        a[i],a[k]=a[k],a[i]

（2）a[i]擂主，攻擂成功擂主与攻擂手交换

n = len(a)
for i in range(n-1):
     # 未定区间[i,n-1]
     for j in range(i+1,n):
        if a[j]<a[i]: 
            a[i],a[j] = a[j],a[i]

找次大值

a = [1,5,3,2,6,4]

#找次最大值 

m_a = a[0]
m_b = a[0]

n = len(a)
for i in range(1, n):
    if a[i] >= m_a :
        m_b = m_a
        m_a = a[i]
    elif a[i] >= m_b:
        m_b = a[i]

print(m_a , m_b)

问题： 求2n个数中的最大值和最小值，最少的比较次数是() A：4n/3 B:2n-2 C:3n-2 D:3n/2

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com