寻找第i个最小的数.cpp

来自「数值分析中常用的几种算法的实现」· C++ 代码 · 共 50 行

#include<stdio.h>
#define Max 30001
int num[Max];
int find(int p,int r,int i)
{
	int x,temp,start,end,k;
	if(p==r)
		return num[p];
	start=p;
	end=r;
	x=num[p];
	while(p<r)
	{
		while(num[r]>x) r--;
		while(num[p]<x) p++;
		if(p<r)
		{
			if(num[r]!=num[p])
			{
				temp=num[r];
				num[r]=num[p];
				num[p]=temp;
			}
			else
			{
				r--;
				p++;
			}
		}
	}
	k=p-start+1;
	if(i<k)
		return find(start,r,i);
	else
		return find(r+1,end,i-k);
}
int main()
{
	int i,n,d;
	for(i=30000;i>=0;i--)
		num[30000-i]=i;
	while(1)
	{
		scanf("%d",&n);
		if(n==0)
			return 0;
		d=find(0,Max-1,n);
		printf("%d\n",d);
	}
}