本文共 1285 字，大约阅读时间需要 4 分钟。

1、问题描述：

对于长度为n的整型数组A，随机生成其数组元素值，然后实现一个线性时间的算法，在该数组中查找其中位数。

2、算法描述：

以原数组中位于中间位置k的元素作为基准值pivot，对原数组进行划分，分别为元素值< pivot、= pivot和> pivot的三部分，将这三部分的元素值分别赋给数组SL、SV、SR，并计算出SL、SV、SR中有效元素的个数sl、sv、sr。将k和sl、sv+sl、sl+sv+sr比较，如果k < sl，说明该数组的中项在SL数组中；如果k < sl+sv，说明该数组的中项在SV中；如果k < sl+sv+sr，说明该数组的中项在SR中。

/*对于长度为n的整型数组A，随机生成其数组元素值，然后实现一个线性时间的算法，在该数组中查找其中项。*/#include 
   
    #include 
    
     using namespace std;int selection(int data[], int n, int k);int main(){	int data[9];	int n = 9;	//随机生成数组元素值	for (int i = 0; i < n; ++i)	{		data[i] = rand();		cout << data[i] << ' ';	}	cout << endl;	if (n & 1)	//如果有奇数个元素	{		cout << selection(data, n, n / 2) << endl;	}	else    //如果有偶数个元素	{		cout << (double(selection(data, n, n / 2) + selection(data, n, n / 2 - 1)) / 2) << endl;	}	return 0;}int selection(int data[], int n, int k)		//data是要查找的数组，n是数组的大小，k是中位数应该在的位置{	//基准值	int pivot = data[k];	//对小于基准值、等于基准值、大于基准值的元素进行划分	int sl = 0, sv = 0, sr = 0;	int SL[10], SV[10], SR[10];	for (int i = 0; i < n; ++i)	{		if (data[i] < pivot)		{			SL[sl] = data[i];			++sl;		}		else if (data[i] == pivot)		{			SV[sv] = data[i];			++sv;		}		else		{			SR[sr] = data[i];			++sr;		}	}	//比较k与子集所含元素大小的关系	if (k < sl)	{		selection(SL, sl, k);	}	else if (k < sv+sl)	{		return data[k];	}	else	{		selection(SR, sr, k - sl - sv);	}}
    
   

转载地址：http://jttai.baihongyu.com/