选定数组中从i到j的第k小的元素(不用对数组排序)

选出数组中从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;
	}
}