寻找T的第k小元素

寻找第n/2小元素--》中值问题

 k=s rs就是第k小元素

k<s rs在左边序列中

k>s rs在右边序列中

#include<iostream>
using namespace std;int Partition(int r[],int low,int high){//对数据进行划分 //无序数组 左边 右边 左小右大int i=low,j=high;while(i<j){//扫描右侧 while(i<j&&r[i]<r[j]) j--; if(i<j){//如果左边比右边的大 就交换 （左小右大）int temp=r[i];r[i]=r[j];r[j]=temp;i++; //移动左边的指针 }//扫描左侧 while(i<j&&r[i]<r[j]) i++;if(i<j){//如果右边比左边的小 就交换 保证左边是小的 右边是大的int temp=r[i];r[i]=r[j];r[j]=temp; j--; //右边的指针向左移动 }}//循环结束i=j时候//返回i的坐标就是中间值 return i;
}int SelectMink(int r[],int k,int low,int high)
{//选择问题的实现 k是待查找的数 int s;//s是要找的轴值 （位置坐标） s= Partition(r,low,high);//如果在中间，就直接返回找到了 ！查找成功 if(s==k){return r[s];}//如果k<r[i] 在左边递归查找else if(k<s){return SelectMink(r,k,low,s-1);}//如果k>r[i] 在右边递归查找 else{return SelectMink(r,k,s+1,high);}
}int main(){cout<<"请输入数据总数："<<endl;int n;cin>>n;int r[n];cout<<"请输入数据:"<<endl;for(int i=0;i<n;i++){cin>>r[i];}int k; //传入的是数据的位置坐标 cout<<"请输入想查找的第k个元素："<<endl;cin>>k;k=k-1; int low=0,high=n-1;int res=SelectMink(r,k,low,high); //要找的是排行老四位置的数是多少 cout<<res; 
}