分治算法在一般选择问题中的应用

Dear 丶 2022-07-11 09:27 83阅读 0赞

最近在啃算法导论，感觉挺有趣的，所以准备写一些博文来记录自己学习中的一些心得。

下面有一个要求就是在一个数组中选取第i小的元素，怎么办?直接排序?然后再输出结果？当然这是一种解决方法，但是效率很低,算法导论中给出了一个比较经典的解决方法:

其过程与快速排序过程中划分类似。每次划分集合可以确定一个元素的最终位置，根据这个位置可以判断是否是我们要求的第i小的元素。如果不是，那么我们只关心划分产出两个子部分中的其中一个，根据i的值来判断是前一个还是后一个，然后接着对子数组进行划分，重复此过程，直到找到第i个小的元素。划分可以采用随机划分，这样能够保证期望时间是θ(n)（假设所有元素是不同的），简言之就是这个算法参考了快排中的一些思路，因为每一次快排之后主元的位置都是已知的，并且主元左边的数都要比他小，右边的数都要比他大，然后我们可以知道主元在数组中是第几大，如果主元大了，那么在左边的子序列中继续上边的步骤，右边的直接丢弃，反之亦然。

举个栗子:

EX:现有集合A=\{32,23,12,67,45,78,10,39,9,58\}，要求其第5小的元素，假设在划分过程中以总是以最后一个元素为主元素进行划分。执行过程如下图所示：

![Image 1][]![Image 1][]![Center][]

RANDOMIZED_SELECT(A,p,r,i)
          if p==r
             then return A[p]
          q = RANDOMIZED_PARTITION(A,p,r)
          k = q-p+1;
           if i==k
              then return A[q]
           else  if i<k
               then return RANDOMIZED_SELECT(A,p,q-1,i)
           else           return RANDOMIZED_SELECT(A,p+1,end,i-k)

再下面是这个算法的具体实现:

public class Main {
    
    	public static void main(String[] args) {
    		int[] a={12,13,56,2,45,76,89,4};
    		int thisone=randommized_selected(a,0,a.length-1,8);
    		System.out.println(thisone);
    	}
    
    	private static int randommized_selected(int[] a, int begin, int end, int j) {
    		
    		if(begin==end){
    			return a[begin];
    		}
    		int p=random_partion(a,begin,end);//以最后一个元素进行划分,p是最后一个元素在序列中的位置
    		int k=p-begin+1;
    		if(j==k){
    			return a[p];
    		}	
    		else if(j<k){
    			return randommized_selected(a,begin,p-1,j);
    		}
    		else
    		return randommized_selected(a, p+1,end, j-k);
    	}
    
    	private static int random_partion(int[] a, int begin, int end) {
    		int i=begin;
    		int j=i-1;
    		for(;i<end;i++)
    		{
    			if(a[i]<=a[end])
    			{
    				j++;
    				int temp=a[i];
    				a[i]=a[j];
    				a[j]=temp;
    			}
    			
    		}
    		j++;
    		int temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
    		return j;
    	}
    
    }

![Center 1][]

[Image 1]: 
[Center]: /images/20220711/8054c1818f734447bd2241f0a1514a7b.png
[Center 1]: /images/20220711/d6f5de8ae1d546fc975d1f34fe90b9a4.png