本文實例講述了Java基於分治算法實現的線性時間選擇操作。分享給大家供大家參考，具體如下：
線性時間選擇問題：給定線性序集中n個元素和一個整數k，1≤k≤n，要求找出這n個元素中第k小的元素，（這裡給定的線性集是無序的）。
隨機劃分線性選擇
線性時間選擇隨機劃分法可以模仿隨機化快速排序算法設計。基本思想是對輸入數組進行遞歸劃分，與快速排序不同的是，它只對劃分出的子數組之一進行遞歸處理。
程序解釋：利用隨機函數產生劃分基準，將數組a[p:r]劃分成兩個子數組a[p:i]和a[i+1:r]，使a[p:i]中的每個元素都不大於a[i+1:r]中的每個元素。接著"j=i-p+1"計算a[p:i]中元素個數j.如果k<=j，則a[p:r]中第k小元素在子數組a[p:i]中，如果k>j，則第k小元素在子數組a[i+1:r]中。注意：由於已知道子數組a[p:i]中的元素均小於要找的第k小元素，因此，要找的a[p:r]中第k小元素是a[i+1:r]中第kj小元素。
在最壞的情況下，例如：總是找到最小元素時，總是在最大元素處劃分，這是時間複雜度為O(n^2) 。但平均時間複雜度與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]; //數組的第一個作為中軸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,kj); } } public static void main(String args[]) { System.out.println("武林網測試結果："); 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("你要查詢的元素是數組中第幾小的？"); @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = r.RandomizedSelect(a,0,8,m); System.out.println("這個數組中第" + m + "小的元素是："+ n); }}運行結果：
更多關於java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。