找第K小元素这个问题，我们第一想到的算法可能是是先预排序，再取第k个。
这个方法很简单，但是却使用大炮打蚊子，大材小用。
因为我们无需知道整个数列，只需知道部分子序列则可。
­
找第K小元素经常联系到的一个问题是找中位数问题：
如果有偶数个，则找第n/2或n/2+1个小元素则可找到中位数；
如果有奇数个，则找第n/2+1个小元素则可找到中位数。
­
以下是找第K小元素的C++代码。
利用的快速排序的思想。
但有区别：
快速排序需要处理两个子序列，而它只需要处理一个。
比较次数的递推式为：O(n)=O(n/2)+(n)
时间复杂度约为O(n).
效率果然高！
­
#include"stdio.h"
int GetMinK(int A[],int n,int k)
{
int s=-1,i=0,j=n-1,temp;
int beg=i;
int end=j;
while(s!=k)
{
  beg=i;
  end=j;
  temp=A[i];
  while(i<j)
  {
   while(i<j&&A[j]>=temp)j--;A[i]=A[j];
            while(i<j&&A[i]<=temp)i++;A[j]=A[i];
  }
  A[i]=temp;
  s=i;
 
  for(int index=0;index<10;index++)printf("%d ",A[index]); printf("\n");
  
  if(s==k)return A[k];
  if(s>k){i=beg;j--;}
  if(s<k){j=end;i++;}
}
}
void main()
{
int A[]={0,-2,3,-4,5,-6,7,80,9,-10};
int k=3;
printf("第%d小元素为：(从0开始)\n%d ",k,GetMinK(A,10,k));
}找第K小元素这个问题，我们第一想到的算法可能是是先预排序，再取第k个。
这个方法很简单，但是却使用大炮打蚊子，大材小用。
因为我们无需知道整个数列，只需知道部分子序列则可。
­
找第K小元素经常联系到的一个问题是找中位数问题：
如果有偶数个，则找第n/2或n/2+1个小元素则可找到中位数；
如果有奇数个，则找第n/2+1个小元素则可找到中位数。
­
以下是找第K小元素的C++代码。
利用的快速排序的思想。
但有区别：
快速排序需要处理两个子序列，而它只需要处理一个。
比较次数的递推式为：O(n)=O(n/2)+(n)
时间复杂度约为O(n).
效率果然高！
­
#include"stdio.h"
int GetMinK(int A[],int n,int k)
{
int s=-1,i=0,j=n-1,temp;
int beg=i;
int end=j;
while(s!=k)
{
  beg=i;
  end=j;
  temp=A[i];
  while(i<j)
  {
   while(i<j&&A[j]>=temp)j--;A[i]=A[j];
            while(i<j&&A[i]<=temp)i++;A[j]=A[i];
  }
  A[i]=temp;
  s=i;
 
  for(int index=0;index<10;index++)printf("%d ",A[index]); printf("\n");
  
  if(s==k)return A[k];
  if(s>k){i=beg;j--;}
  if(s<k){j=end;i++;}
}
}
void main()
{
int A[]={0,-2,3,-4,5,-6,7,80,9,-10};
int k=3;
printf("第%d小元素为：(从0开始)\n%d ",k,GetMinK(A,10,k));
}