find.cpp

在o(n)时间内

//本题首先要感谢黄群同学为我提供了帮助，并且在红皮书《数据结构与算法-学习指导与习题解析》P210找到了答案
//算法描述：先给出一个在0（n）时间内找到序列中第k小的数的算法Search，然后在调用这个算法找中位数，其时间代价也为0（n)的。
//把数组按照每5个一组分为多组，分别排序，然后递归调用算法Search找到这些中位数。利用partition算法，以该中位数为轴值，将数组
//分成两部分，然后在其中一部分元素中递归调用算法Search，找到第k小的元素。
int Search(int * a,int i,int j,int k)//寻找数组a中从i到j中第k小的元素
{
	int p1,m,p2,value;
	if(j - i < 5)
	{
		a = sort(a,i,j - i + 1);//直接插入排序
		value = a[i + k];//找到
	}
	else
	{
		for(m = 0;m < (j - i + 4) / 5;m ++)
		{
			a = sort(a,i + m * 5,5);//分成(j - i + 4) / 5个部分
			a = swap(a,i + m * 5,i + m);//把各部分的中间值换到数组的排序段的前面？i + m * 5不是中间值
		}
		p1 = Search(a,i,i + (j - i + 4) / 5 - 1,(j - i + 4) / 10);//先找到那一部分中间值的中间值
		p2 = partition(a,i,j,p1);//找到轴值p1的位置
		if(k == p2)//找到
			value = a[i + k];
		else if(k < p2)//把中间值位置与k比较
			value = Search(a,i,p2,k);
		else
			value = Search(a,p2,j,k - p2);
	}
	return value;//返回第k小的值
}
void mainsearch(int * a,int n)
{
	int value;
	if(n % 2 == 1)//奇数只有一个中位数
		cout << Search(a,0,n / 2,n - 1) << endl;
	else
	{
		cout << Search(a,0,n / 2,n - 1)<< " ";//偶数有两个中位数
		cout << Search(a,0,n / 2 + 1,n - 1)<< endl;
	}
	return;
}
算法代价评估：设代价为T（n）
分组排序中，每组代价为o（1），共n/5组，所以总共为o(n);
对数组最前面的中值进行排序，代价为T（n/5)。partition算法代价为o（n），再递归调用该算法，代价上限为0（7n/10)。这是
因为n/5个中位数中，有n/10个大于等于p1,而每个5个一组的小数组中又有2个大于等于这个小数组的中位数，则整个数组中至少有3n/10
个大于等于p1，同理至少有3n/10个数小于等于p1,最后用p1划分数组，留下进一步递归的数至多有7n/10个，所以得出其时间代价为：
T(n) <= T(n/5) + o(n) + T(7n/10)
用递归树法解此递归方程，得到T(n) = o(n);