问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。重数最大的元素为该集合的众数。要求使用Partition函数但不能排序。

例如，S={1，2，2，2，3，5}，众数是2，其重数是3。

算法设计：对于给定的多重集S，计算S的众数与重数。

算法思想：采用分治策略 
利用随机选取的划分基准使用划分算法把集合分成大于划分基准以及划分基准以及小于划分基准的三部分。
进而划分为{小于划分基准}{划分基准}{大于划分基准}三个集合，并记录集合的边界下标。
计算{划分基准}集合的长度和下标。
如果{小于划分基准}的集合的长度>{划分基准}集合的长度，则向左递归；
如果{大于划分基准}的集合的长度>{划分基准}集合的长度，则向右递归；
更新{划分基准}集合的长度和下标。

template<typename T>
int Partition(T a[], int p, int r)
{
	int x = a[r];
	int i = p - 1;
	for (int j = p; j <= r; j++)
	{
		if (a[j] <= x) {
			i++;
			if (i != j)swap(a[i], a[j]);
		}
	}
	return i;
}

template<typename T>
int RandomizedPartition(T a[], int p, int r)
{
	srand(time(NULL));
	int i = rand() % (r - p + 1) + p;
	swap(a[i], a[p]);
	return Partition(a, p, r);
}

template<typename T>
void Mode(T a[], int p, int r,int &k,int &index)//k为重数，index为下标
{
	int q = RandomizedPartition(a, p, r);
	int left=q,right=q;//向左向右查找的指针，初始化为q
	while (a[--left] == a[q]);
	while (a[++right] == a[q]);
	left++;
	right--;//以上代码是找到{划分基准}集合的边界下标
	if (k < right - left + 1)
	{//更新k和index
		k = right - left + 1;
		index = q;
	}
	if (left - 1 > k)Mode(a, p, left - 1, k, index);//向左递归
	if (r - right > k)Mode(a, right + 1, r, k, index);//向右递归
}

sorry~ 运行过程后面补充