9.1 最小值和最大值

9.1.1 顺序统计量(Order statistics)

• 在一个由𝑛个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。
  • 最小值是第1个顺序统计量（i=1）
  • 最大值是第n个顺序统计量（i=n）
• 中位数（median）是它所属集合的“中点元素”。
  • 当𝑛为奇数时，中位数位于处；
  • 当𝑛为偶数时，中位数位于和这两处。
  • 不考虑𝑛的奇偶性，下中位数位于处，上中位数位于处。

问题1：寻找最小值或最大值

• 复杂度：最少需要进行n-1次比较

• 伪代码

  Minimum(A)
      min = A[1]
      for i=2 to A.length
          if min > A[i]
              min = A[i]
      return min
  

问题2：同时找到最小值和最大值

• 复杂度：最多次比较就可以同时找到最小值和最大值
• 思路
  • 将一对输入元素相互进行比较。
  • 把较小的元素与当前的最小值进行比较，并更新最小值。
  • 把较大的元素与当前的最大值进行比较，并更新最大值。

9.2 期望为线性时间的选择算法

• 复杂度：最坏情况，期望运行时间
  

• 伪代码

  Randomized-select(A, p, r, i)
  	if p==r
          return A[p]
      q = Randomized-partition(A, p, r)
      k = q-p+1
      if i==k
      	return A[q]
      elif i<k
      	return Randomized-select(A, p, q-1, i)
      else
      	return Randomized-select(A, q+1, r, i-k)
  

• 思路

  • 分：将输入数组A划分成前k-1小的元素，第k小的元素和后n-k小的元素。
  • 治：若i=k，则A[q]即为所求。若i<k，则递归地到前k-1小的元素中选择第i小的元素。若i>k，则递归地到后n-k小的元素中寻找第i-k小的元素。

9.3 最坏情况为线性时间的选择算法

• 复杂度：最坏情况
  
• 思路：通过执行下列步骤，算法SELECT可以确定一个有𝑛>1个不同元素的输入 数组中第𝑖小的元素。（𝑛=1时SELECT直接返回唯一的元素即可）
  • 将输入数组的𝑛个元素划分为每组5个元素的组，以及由剩下的个元素组成的一组（可能没有）。
  • 寻找这组中每一组的中位数。
  • 对第2步中找出的个中位数，递归调用SELECT以找出其中位数x。
  • 以x为主元对数组进行划分，记划分后x的下标为k。
  • 若𝑖=𝑘，则返回𝑥。若𝑖<𝑘，则递归调用SELECT来寻找前𝑘−1个数中的第𝑖小的数。若𝑖>𝑘，则递归调用SELECT 来寻找后𝑛−𝑘个数中第i-k小的数。