求一组数中的第K大数，采用递归方法

参考陈越的《数据结构》，用递归的方法实现寻找一组数中的第K大数。使用了动态数组和清屏函数。

解决思路：

  要想得到第K大的数，用递归的方法拆分
   把一组数按照其中一个数m，分成两批。大于m的一批，小于m一批，

• 若m>=k,则在大于m的一批数中去找
• 若m=k-1;则m即为第k大（递归终止条件）
• 若m<k-1;去小于m的一批数中去找

代码如下：

#include<stdio.h>
#include <stdlib.h>
/*
	Name: 找第K大数 
	Copyright: 
	Author: demosees 
	Date: 23/03/17 19:35
	Description: 找一组数中的第K大，采用递归的方法解决。 
*/
void swap(int *a,int *b)
{
	/*交换两个函数的数值*/
	int temp;
	temp=*b;
	*b=*a;
	*a=temp;
}
int FindKth( int List[],int k,int left,int right)
{
	/*利用递归求第K大的函数*/ 
	/*第一个数字为分隔量*/ 
	int e=List[left];
	int L,R;
	L=left;
	R=right;
	while(1){
	   /*在一个数组中将以基础变量，将数组分成两个部分,大的部分在左边，小的部分在右边*/ 
	    while((List[left]>=e)&&(left<=right)){ 
		left++;
	}
	    while((List[right]<=e)&&(left<right)){ 
		right--;
	}
	
	if (left<right) 
	 swap(&List[left],&List[right]);
	 else break;
   }
   swap(&List[L],&List[left-1]);
    
   if ((left-1-L)>=k)
     /*去左边找第K大*/ 
      return FindKth(List,k,L,left-2);
     else if((left-1-L)<k-1)
     /*去左边找第K大*/ 
	  return FindKth(List,k-left+L,left,R); 
	/*递归终止条件,仅剩一个元素时，就是这个数*/ 
	  else return e;
}

int main()
{
	int K,i;
	int n,*a;
	
	
	/*可以多次输入*/ 
	while(1)
	{ 
	printf("输入要输入数字的个数(若输入0则结束）："); 
	scanf("%d",&n);
	if (!n)
	  break;
	/*申请空间*/   
	a=(int*)malloc(sizeof(int)*n);
	
	/*输入数字*/ 
	printf("依次输入每个数：
");
		for(i=0;i<n;i++)
	  scanf("%d",a+i);
	  
    printf("输入要得到的K大的数
");	  
	scanf("%d",&K);
	/*输出结果*/ 
	printf("%d
",FindKth(a,K,0,n-1));
	 
	 /*释放申请空间*/ 
	 free(a); 
	   
	/*停在屏幕上*/ 
	 //getch();停在屏幕上,读入回车键（方法一） 
	 system("pause"); // 停在屏幕上，调系统函数（方法一） 
    
	/*清屏函数*/ 
	system("cls");
}
	
	return 0;
}