分治法找第K小的数PTA_求第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]);/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29