052364_midnum.cpp

算法设计与分析 求中位数

#include<iostream.h>

int midnum1, midnum2;
void findmid(int m1, int m2, int m3, int m4)//
{
	int temp;
	int a[4] = {m1,m2,m3,m4};
	for (int i = 0; i < 4; i++)
		for (int j = i+1; j < 4; j++)
			if (a[j] <= a[i])
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}

	midnum1 = a[1];midnum2 =a[2];
}
void midnum(int a[], int start1, int end1, int b[], int start2, int end2)
{
	int mid1 = (start1 + end1) / 2;
	int mid2 = (start2 + end2) / 2;
	if (start1 == end1 - 1 && start2 == end2 - 1)
	{
		findmid(a[start1],a[end1],b[start2],b[end2]);
		return ;
	}
	if (a[mid1] == b[mid2])
	{
		midnum1 = a[mid1];
		midnum2 = b[mid2];
		return ;
	}
	else if (a[mid1] > b[mid2])
		midnum(a,start1,mid1,b,mid2,end2);
	else midnum(a,mid1,end1,b,start2,mid2);
}

void main()
{

	int a[19]={2,4,7,9,19,20,25,30,40,48,51,57,60,63,64,70,72,75,90};
	int b[19]={3,5,8,9,12,22,29,58,59,61,62,63,70,73,74,78,80,85,99};
	midnum(a,0,18,b,0,18);
	cout << midnum1 << '\t' << midnum2 << endl;
}





		/*if (a[start1] > b[end2])
		{
			midnum1 = b[end2];
			midnum2 = a[start1];
			return ;
		}
		if (b[start2] < a[start1]  && a[start1] < b[end2])
		{
			midnum1 = a[start1];
			midnum2 = a[end1];
			return ;
		}
		if (a[end1] < b[start2]) 
		{
			midnum1 = a[end1];
			midnum2 = b[start2];
		}
		//if (a[start1] < b[start1])
			//if (a[end1] < )*/