1.第K顺序统计量概念
在一个由n个元素组成的集合中，第k个顺序统计量是该集合中第k小的元素。例如，最小值是第1顺序统计量，最大值是第n顺序统计量。
2.求Top K元素与求第K顺序统计量不同
Top K元素：是指求数组中的最大（或者最小的）K个元素，一般K比较小，采用最大（或者最小）堆实现。之前写过的一篇有关文章是：
海量数据处理的 Top K算法(问题) 小顶堆实现
第K顺序统计量：只求解数组中的第K大元素，是求解一个元素。一般使用“快速排序”的思想，将数组划分求解。
3.第K顺序统计量求解代码
这是求解第K统计量代码，即第k小。如果要求第K大，可以根据数组长度转化为第n-k小。
public class TheK { int array[]={12,435,123,1,345,546,12,546,7,86,354,7}; int paarray(int i,int j) { int pivot=array[i]; //用区间的第1个记录作为基准 while(i<j) { //从区间两端交替向中间扫描，直至i=j为止 while(i<j&&array[j]>=pivot) //pivot相当于在位置i上 j--; if(i<j) array[i++]=array[j]; //相当于交换array[i]和array[j]，交换后i指针加1 while(i<j&&array[i]<=pivot) //pivot相当于在位置j上 i++; if(i<j) array[j--]=array[i]; //相当于交换array[i]和array[j]，交换后j指针减1 } array[i]=pivot; //基准记录已被最后定位 return i; } void getK(int k) { int mid=paarray(0,array.length-1); while(mid!=k) { if(mid<k) mid=paarray(mid+1,array.length-1); else mid=paarray(0,mid-1); } System.out.println("The num of "+k+" is:"+array[k]); } public static void main(String args[]){ //查找第6个元素。数组元素编号从0开始 new TheK().getK(6); } }
