Java对于给定的n个元素的数组a[1..n]，要求从中找出第k小的元素。 【输入样例】 a={20, 43, 32, 67 ,48, 89, 36, 47, 15} k=3

可以使用快速选择算法，它是快速排序算法的变种，时间复杂度为O(n)。具体步骤如下：

1. 随机选择一个元素x，将数组分为左右两部分left和right，其中left中的元素小于等于x，right中的元素大于x。

2. 如果left中元素的个数大于等于k，则在left中递归查找第k小的元素；否则，在right中递归查找第k-left.length个小的元素。

3. 递归终止条件为数组长度为1，直接返回该元素。

Java代码如下：

public static int findKthSmallest(int[] arr, int k) {
return quickSelect(arr, 0, arr.length - 1, k);
}

private static int quickSelect(int[] arr, int left, int right, int k) {
if (left == right) {
return arr[left];
}
int pivotIndex = partition(arr, left, right);
int leftLength = pivotIndex - left + 1;
if (k <= leftLength) {
return quickSelect(arr, left, pivotIndex, k);
} else {
return quickSelect(arr, pivotIndex + 1, right, k - leftLength);
}
}

private static int partition(int[] arr, int left, int right) {
int pivotIndex = left + (right - left) / 2;
int pivotValue = arr[pivotIndex];
int i = left - 1;
int j = right + 1;
while (true) {
do {
i++;
} while (arr[i] < pivotValue);
do {
j--;
} while (arr[j] > pivotValue);
if (i >= j) {
return j;
}
swap(arr, i, j);
}
}

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

// 测试代码
public static void main(String[] args) {
int[] arr = {20, 43, 32, 67, 48, 89, 36, 47, 15};
int k = 3;
System.out.println(findKthSmallest(arr, k)); // 输出 20
}