Top k問題（線性時間選擇算法）

問題描述：給定n個整數，求其中第k小的數。

分析：顯然，對所有的資料進行排序，即很容易找到第k小的數。但是排序的時間複雜度較高，很難達到線性時間，哈希排序可以實作，但是需要另外的輔助空間。

        這裡我提供了一種方法，可以在O(n)線性時間内解決Top k問題。關于時間複雜度的證明，不再解釋，讀者可以查閱相關資料。具體的算法描述如下：

        算法：LinearSelect(S,k)

        輸入：數組S[1:n]和正整數k，其中1<=k<=n；

        輸出：S中第k小的元素

               1. If  n<20  Then  将S中的元素排序後輸出第k個元素，算法結束；

               2.将S劃分為無公共元素的 floor(n/5) 個分組，每組5個元素，第 i 個組記為Si；

               3.用插入排序算法将每個組Si 排序，求得中位數 mi ，其中 i=1,2,3,...,floor(n/5)；

               4.遞歸調用本算法求得｛mi | 1<=i floor(n/5)｝的中位數（即第floor(n/10)小的元素）M；

               5.劃分S為A=｛x|x屬于S 并且 x<M｝， B=｛x|x屬于S 并且 x=M｝和C=｛x|x屬于S 并且 x>M｝；

               6. If |A|>k  Then  輸出 LinearSelect(A,k)；

               7. ElseIf  |A|+|B|<k  Then  輸出 LinearSelect(C,k-|A|-|B|)；

               8. Else   輸出M，算法結束；  

         當然了，本題是求第k小，如果求第k大，可以轉換成對應的第n-k小，同樣可以求。這個算法以後會經常用到，一定要掌握，但是如果資料量不超過20個的話，也可以直接排序求。

         完整的Java代碼如下，代碼寫法都比較通用，讀者可以很容易轉換為其他語言實作：

import java.lang.Math;
import java.util.Arrays;
import java.util.Scanner;
public class Topk {
    public static int LinearSelect(int s[],int n,int k)
    {   int topk=0;
    	if(n<=0)return topk;                          //如果數組為空，則傳回0
        if(n<5)                                      //這裡對應算法的第一步。這裡我定義的是小于5個，則直接排序，讀者也可以自己設定
        {     
       	    for(int i=0;i<n-1;i++)
       	    	for(int j=i+1;j<n;j++)
       	    		if(s[i]>s[j])
       	    		{int t=s[i];s[i]=s[j];s[j]=t;}
        	 topk= s[k-1];
        }
       else{
    	   
        int ss[][]=new int[n/5][5];                  //對應算法的第二步
        int j=-1;
        for(int i=0;i<n/5*5;i++)
        { if(i%5==0)j++;
        	 ss[j][i%5]=s[i];
        	
        } 
        
        int sss[]=new int[n/5];
        for(int i=0;i<n/5;i++)                      //對應算法的第三步
        { 
        	Arrays.sort(ss[i]);
            sss[i]=ss[i][2];
            
        }
        Arrays.sort(sss);
        int M=sss[n/5/2];                           //對應算法的第四步
        
        int A[]=new int[n];                         //對應算法的第五步
        int B[]=new int[n];
        int C[]=new int[n];
        int a=0,b=0,c=0;                      //作為三個結合的指針
        for(int i=0;i<n;i++)                  //放入對應的集合中
         {
        	if(s[i]<M)A[a++]=s[i];
            if(s[i]==M)B[b++]=s[i];
            if(s[i]>M)C[c++]=s[i];
       	 }
       
        if(a>k-1)topk=LinearSelect(A,a,k);             //對應算法第六步，我定義的數組是從下标0開始的忙，是以這裡是k-1
        else if(a+b<k-1)topk=LinearSelect(C,c,k-a-b);  //對應算法第七步
        else topk=M;                                   //對應算法第八步
    	
        }
        return topk;                                  //傳回最終的Top k
    }
	public static void main(String[] args) {
		
     int s[]={16,9,92,40,25,27};
     int n=6;
     int k=2;
     System.out.print("數組為：");
     for(int i=0;i<n;i++)
     {
         System.out.print(s[i]+",");
     }
     System.out.println();
     System.out.println("第"+k+"小的數為："+LinearSelect(s,n,k));
     
	}

}
           

輸出結果為：

數組為：16,9,92,40,25,27,

第2小的數為：16