选择问题——在序列中按顺序找到某个元素。这可以用排序方法做到,即先排个序,在找到指定元素,但是这样就按最快的堆排序、合并排序啥的都得是O(nlgn)数量级的,这里采取的方法可以在期望为O(n)的时间内完成。
具体的做法如同快速排序,因为快速排序最好情况时间也为O(nlogn),但是在实际情况下,遇到的代拍序列并不是最好的。因此,一种改进的方式是快速排序的随机化版本。利用随机化方式应用到该选择问题中,可以是程序期望在在线性时间内完成。
具体的实现方式如下:
int Select(int *A, int begin, int end, int i) { if(begin == end) //如果首尾相同,i一定等于首尾,直接返回指的那个元素即可 { return A[begin]; } int token = RandomizedPartition(A, begin, end), dis; dis = token - begin; if(dis == i) { return A[i]; } else if(dis > i) { Select(A, begin, token-1, i); } else { Select(A, token+1, end, i-dis-1); } }
这里RandomizedPartition()函数返回划分的位置,但是,并不是想随机快速排序一样划分的两个部分都递归调用自身,而是根据具体情况调用一部分。先把RandomizedPartition()写到下面:
View Code
为了便于理解,下面举个具体的例子,看看程序怎么执行。
本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/archive/2013/03/05/2945236.html,如需转载请自行联系原作者