无序数组找第k小的数，直接快速排序，然后通过下表访问即可获得第k小的数字，平均时间复杂度为O（nlgn）
而借助于快排中的划分操作，可以在平均时间复杂度为O（lgn）的限制下找到第k小的数（《算法导论》中“顺序量与中位数”那一章有是时间复杂度的证明）
具体思路：
对数组进行划分操作，返回第一次划分基准值所在的位置index，
a. 如果index=k-1则说明找到了第k小的数，直接返回；
b. 若index>k-1，说明第k小的数在index左边，则继续对index-1及其左边部分进行划分
c. 若index<k-1,则对index+1及其右边部分进行划分
直到index=k-1
具体Java实现代码：
import java.util.Arrays;
public class Middle {
public static void main(String[] args)
{
int[] nums={4,2,1,12,41,21,15,8};
System.out.println(getKthNum(nums,3));
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));
}
public static int getKthNum(int[] nums,int k)
{
if(nums==null||k<1||nums.length<k)
{
return Integer.MIN_VALUE;
}
else
{
int start=0,end=nums.length-1;
int index=partition(nums,start,end);
while(index!=k-1)
{
if(index<k-1)
{
start=index+1;
index=partition(nums,start,end);
}
else
{
end=index-1;
index=partition(nums,start,end);
}
}
return nums[index];
}
}
public static int partition(int[] nums,int start,int end)
{
if(start>end||nums==null||nums.length<end-start+1)
{
return -1;
}
else
{
int key=nums[start];
int i=start,j=end;
while(i!=j)
{
while(j>i&&nums[j]>=key) j--;
while(j>i&&nums[i]<=key) i++;
if(j>i)
{
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
nums[start]=nums[i];
nums[i]=key;
return i;
}
}
}