随机选择问题算法说明

问题描述

问题描述：寻找第k小元素的一个直接方法是对所有的元素排序并取出第k小的元素，这个方法需要Ω（n log n）时间，因为任何基于比较的排序过程在最坏情况下必须至少要花这么多时间。一个具有n个元素的集合中，第k小元素能够在最优线性时间内找到，这个问题也称为选择问题。其基本思想如下：假设递归算法中，在每个递归调用的划分步骤后，我们丢弃元素的一个固定部分并且对剩余的元素递归，则问题的规模以几何级数递减，也就是在每个调用过程中，问题的规模以一个常因子被减小。

随机选择问题，首先随机产生一个数组A中的元素x，然后将数组划分成三个数组：A1，A2和A3，其中分别包含小于，等于和大于x的元素。接着求出第k小元素出现在三个数组中的哪一个，并根据测试的结果，算法或返回第k小的元素，或者在A1或A3上递归。

问题分析

对于算法select ，我们已经证明了算法的运行时间是Θ（n），具有一个很大的常系数使得算法变得不切实际，特别是对小的和中等的n值也如此。所以现在对选择给出一个既简单又快捷的随机Las Vegas选择算法，它的期望运行时间是一个带有小的常系数的Θ（n）。正如算法RANDOMIZEDSELECT一样，在最坏情况下它的运行时间是Θ（n2），而且最坏情况的界限也和算法求解的实例无关，它只是一个由随机数发生器选择的一个不凑巧的序列的结果，它发生的概率是非常小的。算法的运作在下述意义上像二分搜索算法一样，不断丢弃输入的一部分直到所求第k个最小元素已经得出。算法精确描述在RANDOMIZEDSELECT中给出。

算法描述

算法RANDOMIZEDSELECT

输入：n个元素的数组A[1…n]和整数k，1<=k<=n。

输出：A中的第k小元素。

1.rselect(A,1,n,k)

过程 rselect(A,low,high,k)

1.v = random(low,high)

2.x = A[v]

3.将A[low,high]分成三个数组

A1 = {a|a

A2 = {a|a=x}

A3 = {a|a>x}

4.case

|A1|〉=k: return rselect(A1,1, |A1|,k)

|A1|+|A2|>=k: return x

|A1|+|A2|return rselect(A3,1, |A3|,k-|A1|-|A2|)

5.end case

结果分析

实验结果：为了检查程序和察看结果，这里选择了一个实例：寻找一下25个元素的第13小元素：8 33 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 29 32 54 5 16 22 23 7。

程序运行结果截图如下：

改进前运行结果截图：

程序简单修改后（加上带注视//的语句），可输出每一次产生随机数组元素。并且每一次丢弃一部分元素后，都输出得到的新数组和新的k值。（输出中间结果可以帮助理解）

为了说明程序的随机性，下面给出两张改进后的截图：

截图1：

截图2：