分治法找第K小的数PTA

分治法————找第K小的数

基本思路：用一个基准数a(本题选用数组的第一个元素作为基准数)将S分割为两部分，分别为小于等于a的S1和大于a的S2.记|S1|表示S1中元素的个数，|S2|表示S2中元素的个数。这样当|S1|>k时，那么第k小的数在S1中并且时S1中第k小的数；相反的，当|S1|<k时，那么第k小的数在S2中并且时S2中第k-S1小的数；而当S1=k时，那么这个第k小的数就是基准数本身。

#include <stdio.h>
 #define MAXN 10000
 
 void swap(int *x,int *y)
 {
  int temp;
  temp = *x;
  *x = *y;
  *y = temp;
 }
int partition(int a[],int left,int right)
{
 int e = a[left];
 int L=left,R=right;
 int temp=0;
 
 while(1){
  while(left<=right && e>=a[left]){/*从左向右遍历直到找到比基准数大的数停止*/ 
   left ++; 
  }
  while(left<right && e<a[right]){/*从右向左遍历直到找到比基准数小的数停止*/ 
   right --;
  }
  if(left < right){
   swap(&a[left],&a[right]);/*将左边比基准数大的数与右边比基准数小的数互换，使得左边全是比基准数小的数，右边全是比基准数大的数*/ 
     }
  else
   break;/*当left=right时，此时来到了边界，跳出循环*/ 
 }
 swap(&a[L],&a[left-1]);/*因为a[left-1]比基准数小所以应该将他换到基准数左边，二基准数时S1中最大数*/ 
 
 return left;/*此处的left等价于|S1|*/
 
}
int find(int a[],int left,int right,int k)
{
 int pos =partition(a,left,right);
 if(pos > k)/*当|S1|>k时则第k小的数在S1中*/
  find(a,left,pos-1,k);/*在S1中找第k小的数*/ 
 else if(pos < k)/*当|S1|<k时则第k小的数在S2中*/ 
  find(a,pos,right,k);/*在S2中找第k小的数*/ 
 else/*当|s1|=k时则基准数就是第k小的数*/ 
  return a[pos-1];
  
}
 int main(void){
  int n,k;
  scanf("%d %d",&n,&k);
  
  int a[MAXN];
  int i;
  for(i=0; i<n; i++)
   scanf("%d",&a[i]);
  
  int num;
  num = find(a,0,n-1,k);
  
  printf("%d",num);
  
   
  return 0;
 }