BFPRT算法解決的問(wèn)題十分經(jīng)典，即從某n個(gè)元素的序列中選出第k大（第k?。┑脑?，通過(guò)巧妙的分 析，BFPRT可以保證在最壞情況下仍為線(xiàn)性時(shí)間復(fù)雜度。
該算法的思想與快速排序思想相似，當(dāng)然，為使得算法在最壞情況下，依然能達(dá)到o(n)的時(shí)間復(fù)雜 度，五位算法作者做了精妙的處理

  算法步驟：

              1. 將n個(gè)元素每5個(gè)一組，分成n/5(上界)組。

              2. 取出每一組的中位數(shù)，任意排序方法，比如插入排序。

              3. 遞歸的調(diào)用selection算法查找上一步中所有中位數(shù)的中位數(shù)，設(shè)為x，偶數(shù)個(gè)中位數(shù)的情況下設(shè)定為選取中間小的一個(gè)。

              4. 用x來(lái)分割數(shù)組，設(shè)小于等于x的個(gè)數(shù)為k，大于x的個(gè)數(shù)即為n-k。

              5. 若i==k，返回x；若i<k，在小于x的元素中遞歸查找第i小的元素；若i>k，在大于x的元素中遞歸查找第i-k小的元素。

終止條件：n=1時(shí)，返回的即是i小元素。

圖解

Paste_Image.png

線(xiàn)性查找就是從數(shù)組的起始位置a[0]開(kāi)始依次比較數(shù)組中的每一個(gè)值直到找到目標(biāo)值，當(dāng)然也有可能循環(huán)遍歷了數(shù)組中所有值也沒(méi)找到目標(biāo)值。

代碼

  public class LinearSearchDemo { 
                public static void main(String[] args) { 
                        int[] data = {2, 1, 4, 6, 12, 7}; 
                        int target = 12; 
                        int searchIndex = search(data, target); 
                        if (searchIndex != -1) { 
                              System.out.println("found at: " + searchIndex); 
                        }else { 
                              System.out.println("not found"); 
                        } 
                } 
          /*
           *@param data 待查找的數(shù)組 
           *@param target 待查找的值 
           *@return int 目標(biāo)值在數(shù)組中的索引，如果沒(méi)找到返回-1  
           */
         public static int search(int[] data, int target) { 
                        int length = data.length; 
              //從頭遍歷數(shù)組中的各個(gè)值，如果找到目標(biāo)值就返回其索引 
                      for (int i = 0; i < length; i++) { 
                                if (data[i] == target) { 
                                          return i; 
                                } 
                      }
            //代碼能走到這一步就說(shuō)明上面的循環(huán)遍歷結(jié)束了也沒(méi)找到目標(biāo)值 //即目標(biāo)值不存在于數(shù)組中
                       return -1; 
          }
      }
    輸出結(jié)果：found at: 4