选出数组中从i到j的第k小的元素(不用对数组排序)
package com.flyingh.demo;import java.util.Random;public class Demo {public static void main(String[] args) {int[] arr = { 3, 6, 5, 8, 7, 2, 1, 9, 0, 4 };System.out.println(select(arr, 1, 8, 5));}public static int select(int[] arr, int i, int j, int k) {if (k < 1 || k > j - i + 1) {return -1;}// int t = randomizedPartition(arr, i, j);int t = randomizedPartition2(arr, i, j);if (t == i + k - 1) {return arr[t];} else if (t < i + k - 1) {return select(arr, t + 1, j, k + i - 1 - t);} else {return select(arr, i, t, k);}}private static int randomizedPartition2(int[] arr, int m, int n) {int t = new Random().nextInt(n + 1 - m) + m;int tmp = arr[t];arr[t] = arr[n];arr[n] = tmp;int i = m - 1;for (int j = m; j < n; ++j) {if (arr[j] < arr[n]) {int temp = arr[++i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[n];arr[n] = temp;return i + 1;}@SuppressWarnings("unused")private static int randomizedPartition(int[] arr, int m, int n) {int t = new Random().nextInt(n + 1 - m) + m;int tmp = arr[m];arr[m] = arr[t];arr[t] = tmp;int key = arr[m];while (m < n) {while (m < n && arr[n] >= key) {--n;}arr[m] = arr[n];while (m < n && arr[m] <= key) {++m;}arr[n] = arr[m];}arr[m] = key;return m;}}