关于算法:算法线性时间复杂度的查找算法

给定一无序数组a[],求第k小的数

public static int randomPartition(int a[], int low, int high) {  int len = high - low + 1;  Random rand = new Random();  int r = rand.nextInt(len) + low;  int temp = a[r];  a[r] = a[high];  a[high] = temp;  int i = low - 1, j = low;  int key = a[high];  for (; j < high; j++) {    if (a[j] <= key) {      i++;      int temp1 = a[j];      a[j] = a[i];      a[i] = temp1;    }  }  i++;  a[j] = a[i];  a[i] = key;  return i;}public static int randomSelect(int a[], int low, int high, int i) {  if (low == high) {    return a[low];  }  int q = randomPartition(a, low, high);  int k = q - low + 1;  if (i == k)    return a[q];  else if (i < k)    return randomSelect(a, low, q - 1, i);  else return randomSelect(a, q + 1, high, i - k);}

工夫复杂度O(n)