【答案解析】问题描述：给定一个无序的数组，从一个数组中找出第k个最小的数，例如，对于给定数组序列{1，5，2，6，8，0，6}，其中第4小的数为5。
方法一：排序法
最容易想到的方法就是对数组进行排序，排序后的数组中第k-1个位置上的数字即为数组的第k个最小的数(原因是数组下标从0开始计数)，这种方法最好的时间复杂度为O(nlogn)。
方法二：“剪枝”法
采用快速排序的思想来实现。主要思路如下：选一个数tmp=a[n-1]作为枢纽，把比它小的数都放在它的左边，比它大的数都放在它的右边，然后判断tmp的位置，如果它的位置为k-1，那么它就是第k个最小的数；如果它的位置小于k-1，那么说明第k个小的元素一定在数组的右半部分，采用递归的方法在数组的右半部分继续查找；否则第k个小的元素在数组的左半部分，采用递归的方法在左半部分数组中继续查找。示例如下：
public class Test{
public static int quikSort(int array[], int low, int high, int k){
int i, j;
int tmp;
if(low＞high)
return Integer.MIN_VALUE;
i=low+1;
j=high;
tmp=array[i];
while(i＜j){
while(i＜j&&array[j]＞=tmp)
j--;
if(i＜j)
array[i++]=array[j];
while(i＜j&&array[i]＜tmp)
i++;
if(i＜j)
array[j--]=array[i];
}
array[i]=tmp;
if(i+1==k)
return tmp;
else if(i+1＞k)
return quikSort(array, low, i-1, k);
else
return quikSort(array, i+1, high, k);
}
public static int getKMin(int array[], int k){
if(array==null)
return Integer.MIN_VALUE;
if(array.length＜k)
return Integer.MIN_VALUE;
return quikSort(array, 0, array.length-1, k);
}
public static void main(String[]args){
int a[]={1, 5, 2, 6, 8, 0, 6};
int kMin=getKMin(a, 4);
System.out.println(kMin);
}
}
程序运行结果为：
5
表面上看起来这种方法还是在对数组进行排序，但是它比排序法的效率高，主要原因是当在数组右半部分递归查找时，完全不需要关注左半部分数组的顺序，因此省略了对左半部分数组的排序。因此，这种方法可以被看作一种“剪枝”方法，不断缩小问题的规模，直到找到第k个小的元素。