2.4.4  查找数组中第k个最小值

在查找算法讨论的最后，我们介绍一个更复杂的问题。尽管此时可以跳过这一示例，但第11章讲到排序算法时将用到这个算法的一些特征。

在前面两例中介绍了在任意数组中查找最大值的递归方法，以及在有序数组中查找任意值的递归方法。这个示例描述在任意数组anArray中查找第k个最小值的递归解决方案。您是否曾经对这类值有兴趣呢？统计学家经常需要数据集合的中值。在有序的数据集合中，中值位于集合中央。在无序的数据集合中，小于中值的值的数目与大于中值的值的数目大致相等。因此，如果有49个值，则第25个最小值是中值。

很明显，可通过对数组排序来解决这个问题。这样，第k个最小值将是anArray[k-1]。虽然这是一个可行的解决方案，但所需工作量大，应该还有效率更高的算法。这里讲述的解决方案在不对数组排序的情况下查找第k个最小值。

到目前为止已经知道，可以根据一个或多个同类型的更小问题编写解决方案，递归地解决一个问题。在这种方法中，"更小"这一概念能够确保到达基例。对于前面所有的递归解决方案，递归调用的问题规模缩减是可预见的。例如，阶乘函数总是将问题规模减1，折半查找总是将问题规模减半。另外，除折半查找外，前面所有问题的基例都有一个不变的、预定义的规模。这样，只要了解原始问题的规模，就能确定在到达基例前所需的递归调用的数目。

查找第k个最小值的解决方案与这些技术不同。虽然可以根据较小问题来解决问题，但问题的缩减程度取决于数组中的值，因此无法提前知道这一信息。此外，与折半查找一样，该方案的基例规模取决于数组中元素的值(在折半查找中，当中间值是需要查找的值时就到达了基例)。

注释：在前面所有示例中，可以知道每次递归调用时问题规模的减少量

这种解决方案之所以"不可预见"，是由问题本质造成的：项在数组的任何预定义部分的顺序与项在整个数组中的顺序没有必然关系，不能由此确定第k个最小值。例如，假设anArray包含如图2-14所示的值。注意，6在anArray[3]中，是anArray前半部分的第3个最小值；8在anArray[4]中，是anArray后半部分的第3个最小值。通过这些观察，能得出在整个anArray数组中第3个最小值的位置吗？回答是否定的；使用数组的一部分，不能得出与整个数组有关的任何结论。应尝试其他固定的拆分方案。

注释：在查找第k个最小值问题的递归解决方案中，既无法预测较小问题的规模，也无法预测基例的规模

递归解决方案过程为：

(1) 在数组中选择枢轴(pivot)值

(2) 根据枢轴值，合理排列(或划分)数组中的值

(3) 将策略递归地用于一个分区

假定想查找数组段anArray[first..last]中的第k个最小值。假设枢轴p是数组段中的任意值(暂时忽略选择p的方式)，将数组anArray[first..last]的值分为3个区域：S1，其中包含的值小于等于p；枢轴p本身；S2，其中包含的值大于等于p。这种划分方法意味着S1中的所有值不会比S2中的值大，如图2-15所示。

注释：将anArray划分为3个部分：值小于等于p、p、值大于等于p

anArray[first..pivotIndex-1]中的所有值小于等于p，anArray[pivotIndex+1..last]中的所有值大于等于p。注意，区域S1和S2的大小取决于p和anArray[first..last]的其他值。

这种划分得到了3个更小问题，因此解决其中一个问题就可以解决原始问题：

1. 若S1包含k或更多值，则S1包含数组段anArray[first..last]的第k个最小值。第k个最小值一定在S1中。由于S1是数组段anArray[first..pivotIndex-1]，若k<pivotIndex-first+1，则将出现这种情况。

2. 若S1包含k-1个值，则第k个最小值一定是枢轴p。这是基例。若k=pivotIndex-first+1，则出现这种情况。

3. 若S1包含的值数少于k-1，则数组anArray[first..last]的第k个最小值一定在S2中。因为S1包含pivotIndex-first个值，所以anArray[first..last]中的第k个最小值是S2中的第k-(pivotIndex-first+1)个最小值。若k>pivotIndex-first+1，则出现这种情况。

可以用一个递归定义来总结上述讨论。令：
 

kSmall(k, anArray, first, last) = anArray[first..last]的第k个最小值 

在选择枢轴值p，并将anArray[first..last]分为S1和S2后，可得到kSmall(k, anArray, first, last)等于
 

总有一个枢轴；由于它既不属于S1也不属于S2，因此每次递归被查找数组段的大小至少减1。这样最终将到达基例：要查找的值是枢轴。下面给出了伪代码解决方案：
 

// Returns the kth smallest value in anArray[first..last].  
kSmall(k: integer, anArray: ArrayType,  
first: integer, last: integer): ValueType  
Choose a pivot value p from anArray[first..last]  
Partition the values of anArray[first..last] about p  
if (k < pivotIndex - first + 1)  
return kSmall(k, anArray, first, pivotIndex - 1)  
else if (k == pivotIndex - first + 1)  
return p  
else  
return kSmall(k - (pivotIndex - first + 1), anArray,  
pivotIndex + 1, last) 

注释：anArray[first..last]中的第k个最小值

以上伪代码可以很方便地转换为C++函数。唯一的问题是如何选择枢轴值p，以及如何根据所选的p划分数组。p可以任意选择。数组中的任何p都可以，但这一选择将影响到达基例的速度。第11章将给出一个根据p划分值的算法，到时候还将介绍如何将kSmall函数转换为排序算法。