Java基于分治算法實現(xiàn)的線性時間選擇操作示例

更新時間：2017年11月24日 08:56:03 作者：萌神哆啦A夢

這篇文章主要介紹了Java基于分治算法實現(xiàn)的線性時間選擇操作,涉及java排序、比較、計算等相關操作技巧,需要的朋友可以參考下

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

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

隨機劃分線性選擇

線性時間選擇隨機劃分法可以模仿隨機化快速排序算法設計?；舅枷胧?span style="color: #ff0000">對輸入數(shù)組進行遞歸劃分，與快速排序不同的是，它只對劃分出的子數(shù)組之一進行遞歸處理。

程序解釋：利用隨機函數(shù)產(chǎn)生劃分基準，將數(shù)組a[p:r]劃分成兩個子數(shù)組a[p:i]和a[i+1:r]，使a[p:i]中的每個元素都不大于a[i+1:r]中的每個元素。接著"j=i-p+1"計算a[p:i]中元素個數(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小元素。

在最壞的情況下，例如：總是找到最小元素時，總是在最大元素處劃分，這是時間復雜度為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];  //數(shù)組的第一個作為中軸
    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("腳本之家測試結果：");
    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("你要查詢的元素是數(shù)組中第幾小的？");
    @SuppressWarnings("resource")
 Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    int n = r.RandomizedSelect(a,0,8,m);
    System.out.println("這個數(shù)組中第" + m + "小的元素是："+ n);
  }
}

運行結果：