9.1 最小值和最大值

伪代码 过程 MINIMUM(A)
MINIMUM(A)
  min = A[1]
  for i = 2 to A.length
    if min > A[i]
      min = A[i]
  return min

同时找到最大值和最小值

事实上，我们只需要最多3⌊n/2⌋次比较就可以同时找到最小值和最大值。具体的方法是记录已知的最小值和最大值。但我们并不是将每一个输人元素与当前的最小值和最大值进行比较——这样做的代价是每个元素需要2次比较，而是对输入元素成对地进行处理。首先，我们将一对输人元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，对每两个元素共需3次比较。

如何设定已知的最小值和最大值的初始值依赖于n是奇数还是偶数。如果n是奇数，我们就将最小值和最大值的初值都设为第一个元素的值，然后成对地处理余下的元素。如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与n是奇数的情形一样，成对地处理余下的元素。

下面来分析一下总的比较次数。如果n是奇数，那么总共进行3⌊n/2⌋次比较。如果n是偶数，则是先进行一次初始比较，然后进行3(n一2)/2次比较，共3n/2-2次比较。因此，不管是哪一种情况，总的比较次数至多是3⌊n/2⌋。

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

伪代码
RANDOMIZED-SELECT(A,p,r,i)
  if p == r//检查递归的基本情况，即A[p..r]中只包括一个元素
    return A[p]//将A[p]返回作为第i小的元素
  q = RANDOMIZED-PARTITION(A,p,r)//将数组A[p..r]划分为两个（可能为空的）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于或等于A[q],而A[q]小于A[q+..r]中的每个元素【A[q]为主元(pivot)】
  k = q - p + 1//计算子数组[p..q]内的元素个数k，即处于划分的低区的元素的个数加1，这个1指主元
  if i == k//the pivot value is the answer//检查A[q]是否是第i小的元素
    return A[q]
  //否则，算法要确定第i小的元素落在两个子数组A[p..q-1]和A[q+1..r]的哪一个之中
  else if i< k
    return RANDOMIZED-SELECT(A,p,q-1,i)//要找的元素落在划分的低区中
  else return RANDOMIZED-SELECT(A,q+1,r,i-k)//要找的元素落在划分的高区中

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

通过执行下列步骤，算法SELECT可以确定一个有n>1个不同元素的输入数组中第i小的元素。(如果n=1，则SELECT只返回它的唯一输入数值作为第i小的元素。)

  1. 将输入数组的n个元素划分为⌊n/5⌋组，每组5个元素，且至多只有一组由剩下的n mod5个元素组成。
  2. 寻找这⌈n/5⌉组中每一组的中位数:首先对每组元素进行插入排序， 然后确定每组有序元素的中位数。
  3. 对第2步中找出的⌈n/5⌉个中位数，递归调用SELECT 以找出其中位数x(如果有偶数个中位数，为了方便，约定工是较小的中位数)。
  4. 利用修改过的PARTITION版本，按中位数的中位数x对输入数组进行划分。让k比划分的低区中的元素数目多1，因此x是第k小的元素，并且有n一k个元素在划分的高区。
  5. 如果i=k，则返回x。如果i<k，则在低区递归调用SELECT来找出第i小的元素。如果i>k，则在高区递归查找第i一k小的元素。
形象的说明

alt

alt

9.3-3

alt

Solution

我们可以通过使用“快速选择”将轴心元素选择为精确的中间值，从而修改快速排序以在最坏的nlgn时间情况下运行。然后，我们可以保证我们的轴心是好的，并且找到中间值所花费的时间与其余分区的顺序相同。

9.3-5

alt

Solution

要使用它，只需找到中间值，根据该中间值对数组进行分区。

  • 如果i小于原始数组长度的一半，则在前半部分递归。
  • 如果i是数组长度的一半，则返回来自中间查找黑框的元素。
  • 如果i大于数组长度的一半，则减去数组长度的一半，然后在数组的后半部分递归。

9.3-7

alt

Solution

求O（n）中的中值；创建一个新数组，每个元素的绝对值都是原始值减去中值；求O（n）中的第k个最小数，则所需值是与中位数的绝对差值小于或等于新数组中第k个最小数的元素。