select.cpp

《计算机算法基础》关于选择问题算法：找第k小元素

#include <iostream.h>
#include<stdlib.h>
#include<strstrea.h>
int A[100];
int partition(int  m,int  p){
        int v,i,tem;
        v=A[m];i=m;
        while(1){
            do{i=i+1;}while(A[i]<=v);
            do{p=p-1;}while(A[p]>v);
            if(i<p){
                tem=A[i];A[i]=A[p];A[p]=tem;
            }else break;
        }
        A[m]=A[p];A[p]=v;return p;
}

void select(int n,int k){
	int j,m,r;
	m=1;r=n+1;
    while(1){
		j=r;
		j=partition(m,j);
		if(k==j)break;
		else if(k<j)r=j;
		else m=j+1;
	}
}

void main(){
	int i=0,tem,j;
	A[i]=0;
	cout<<"输入整数数组以-1(n>4)结束：";
	while(1){
		cin>>tem;
		if(tem==-1)break;
		A[++i]=tem;
	}A[i+1]=1000;
	for(j=1;j<=i;j++){
		select(i,j);
	    cout<<"第"<<j<<"小元素为："<<A[j]<<endl;
	}
	
}