//本題首先要感謝黃群同學為我提供了幫助，并且在紅皮書《數據結構與算法-學習指導與習題解析》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);