找第k小算法程序.rar_K.

#include<iostream.h> #include<string.h> int process(int start,int tail,int b[]); int find(int start,int tail,int k,int b[]); void main()/*数列的第一个数和最后一个数不能相等，除非所有数都相等*/ { int s; int a,*b; cout<<"输入数据的个数："<<endl; cin>>s; cout<<"输入数据："<<endl; b=new int[s]; for(int i=0;i<s;i++) cin>>b[i]; cout<<"输入查找第几小的数："<<endl; cin>>a; cout<<"第"<<a<<"小的数为："; cout<<find(0,s-1,a,b)<<endl; cout<<"目前数列顺序为："<<endl; for(i=0;i<s;i++) cout<<b[i]<<" "; cout<<endl; } int process(int start,int tail,int b[])/*将数列分成以n/2为界线前半部分和后半部分，前半部分所有的数都小于后半部分任意一数*/ { int i,j,temp,x; i=start; j=tail; x=b[i]; do { while(b[j]>=x && j>i) j=j-1; if(j>i) { temp=b[i]; b[i]=b[j]; b[j]=temp; } while(b[i]<=x && i<j) i=i+1; if(i<j) { temp=b[j]; b[j]=b[i]; b[i]=temp; } } while(i!=j); b[i]=x; return i; } int find(int start,int tail,int k,int b[]) { int p,q; if(start==tail) return b[start]; else { p=process(start,tail,b); q=p-start+1; if(k<=q) return find(start,p,k,b);/*在前半部分查找*/ else return find(p+1,tail,k-q,b);/*在后半部分查找*/ } }