博客

可以用简单选择排序或者冒泡找出第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;
}