可以用简单选择排序或者冒泡找出第k大的元素，当N很大时时间复杂度趋近于O（N） 也可以用堆排序选出来，时间复杂度O（K Log N） 最优解使用快排，时间复杂度O（N） 用快排划分成两个子集，且当前界限为第x大，若 x > k ，则要找元素为x左边子集中第x-k大的元素，若 x < k ，则要找元素在x右边子集，为第k大元素，若 x = k， 划分元素即为所求，代码：
#include<stdio.h> #include<stdlib.h> int Partition(int A[],int low,int high){ int pivot = A[low]; while(low < high){ while(low < high && A[high] > pivot) high--; A[low] = A[high]; while(low < high && A[low] < pivot) low++; A[high] = A[low]; } A[low] = pivot; return low; } int Select_k(int A[],int low,int high,int k){ int index; if(low == high) return A[low]; int pivot = Partition(A,low,high); index = high - pivot + 1;//index标识当前划分界限这个数第几大 if(index == k) return A[pivot]; else if(index < k) Select_k(A,low,pivot-1,k-index);//从左边找第k-index大的数 else Select_k(A,pivot+1,high,k); //从右边找第k大的数 } int main(){ int A[] = {10,9,8,7,6,5,4,3,2,1}; printf("%d",Select_k(A,0,9,3)); return 0; }