本文實(shí)例講述了Java基于分治算法實(shí)現(xiàn)的線(xiàn)性時(shí)間選擇操作。分享給大家供大家參考，具體如下：

創(chuàng)新互聯(lián)建站是一家集網(wǎng)站建設(shè),西盟企業(yè)網(wǎng)站建設(shè),西盟品牌網(wǎng)站建設(shè),網(wǎng)站定制,西盟網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷(xiāo),網(wǎng)絡(luò)優(yōu)化,西盟網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M(mǎn)足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專(zhuān)業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶(hù)成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

線(xiàn)性時(shí)間選擇問(wèn)題：給定線(xiàn)性序集中n個(gè)元素和一個(gè)整數(shù)k，1≤k≤n，要求找出這n個(gè)元素中第k小的元素，（這里給定的線(xiàn)性集是無(wú)序的）。

隨機(jī)劃分線(xiàn)性選擇

線(xiàn)性時(shí)間選擇隨機(jī)劃分法可以模仿隨機(jī)化快速排序算法設(shè)計(jì)?；舅枷胧菍?duì)輸入數(shù)組進(jìn)行遞歸劃分，與快速排序不同的是，它只對(duì)劃分出的子數(shù)組之一進(jìn)行遞歸處理。

程序解釋?zhuān)豪秒S機(jī)函數(shù)產(chǎn)生劃分基準(zhǔn)，將數(shù)組a[p:r]劃分成兩個(gè)子數(shù)組a[p:i]和a[i+1:r]，使a[p:i]中的每個(gè)元素都不大于a[i+1:r]中的每個(gè)元素。接著"j=i-p+1"計(jì)算a[p:i]中元素個(gè)數(shù)j.如果k<=j，則a[p:r]中第k小元素在子數(shù)組a[p:i]中，如果k>j，則第k小元素在子數(shù)組a[i+1:r]中。注意：由于已知道子數(shù)組a[p:i]中的元素均小于要找的第k小元素，因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。

在最壞的情況下，例如：總是找到最小元素時(shí)，總是在大元素處劃分，這是時(shí)間復(fù)雜度為O(n^2)。但平均時(shí)間復(fù)雜度與n呈線(xiàn)性關(guān)系，為O(n)

package math;
import java.util.Scanner;
import java.util.Random;
public class RandomSelect {
  public static void swap(int x, int y) {
    int temp = x;
    x = y;
    y = temp;
  }
  public int Random (int x, int y) {
    Random random = new Random();
    int num = random.nextInt(y)%(y - x + 1) + x;
    return num;
  }
  public int partition(int[] list, int low, int high) {
    int tmp = list[low];  //數(shù)組的第一個(gè)作為中軸
    while (low < high) {
      while (low < high && list[high] > tmp) {
        high--;
      }
      list[low] = list[high];  //比中軸小的記錄移到低端
      while (low < high && list[low] < tmp) {
        low++;
      }
      list[high] = list[low];  //比中軸大的記錄移到高端
    }
    list[low] = tmp;       //中軸記錄到尾
    return low;          //返回中軸的位置
  }
  public int RandomizedPartition (int[] arrays, int left, int right) {
    int i = Random(left, right);
    swap(arrays[i], arrays[left]);
    return partition(arrays, left, right);
  }
  public int RandomizedSelect(int[] arrays, int left, int right, int k) {
    if(left == right ) {
      return arrays[left];
    }
    int i = RandomizedPartition(arrays, left, right);
    int j = i - left + 1;
    if(k <= j) {
      return RandomizedSelect(arrays,left, i,k) ;
    }
    else {
      return RandomizedSelect(arrays,i+1,right,k-j);
    }
  }
  public static void main(String args[]) {
    System.out.println("創(chuàng)新互聯(lián)測(cè)試結(jié)果：");
    int[] a = {7,5,3,4,8,6,9,1,2};
    for (int i = 0; i < 9; i ++) {
      System.out.print(a[i]+ " ");
    }
    System.out.println();
    RandomSelect r = new RandomSelect();
    System.out.println("你要查詢(xún)的元素是數(shù)組中第幾小的？");
    @SuppressWarnings("resource")
 Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    int n = r.RandomizedSelect(a,0,8,m);
    System.out.println("這個(gè)數(shù)組中第" + m + "小的元素是："+ n);
  }
}

新聞名稱(chēng)：Java基于分治算法實(shí)現(xiàn)的線(xiàn)性時(shí)間選擇操作示例-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://weahome.cn/article/cegjcc.html