quickselect.cpp

来自「这是一个利用遗传算法求解函数极值」· C++ 代码 · 共 41 行

#include "stdafx.h"

#include "QuickSelect.h"

int Partition(double A[],int left,int right)
{
	int i=left,
	    j=right+1;
	double x=A[left],
		   dtemp;
	while(1)
	{
		while(A[++i]>x);
		while(A[--j]<x);
		if(i>=j) break;

		dtemp=A[i];
		A[i]=A[j];
		A[j]=dtemp;
	}
	A[left]=A[j];
	A[j]=x;
	return j;   
}

double QuickSelect(double A[],int left,int right,int k)
{
	if(left==right)
		return A[left];
	int i=Partition(A,left,right),
     	j=i-left+1;
	if(k<=j) 
	{
		if(k=j)
			return A[i];
		else
			return QuickSelect(A,left,i,k);
	}
	else
		return QuickSelect(A,i+1,right,k-j);
}