#include?“iostream.h“
#include?“stdlib.h“
#include?“time.h“
#define?M?20

/*modalnumber用來表示眾數(shù)*/
int?modalnumber=0;
/*multiplicity用來表示該眾數(shù)的重數(shù)*/
int?multiplicity=0;

/*
	函數(shù)名：Partition
	作用：對數(shù)組進行分解（與快速排序的分解思想類似）
*/
int?Partition（int?a[]int?pint?r）
{
	//在a[p]到a[r-1]中隨機選擇一個元素作為主元
//	srand（time（0））;
//	int?x=a[rand（）%（r-p）+p];
	int?x=a[r-1];
	int?i=p-1;
	int?temp;
	for（int?j=p;j<=r-2;j++）
	{
		if（a[j]<=x）
		{
			i++;
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	temp=a[i+1];
	a[i+1]=a[r-1];
	a[r-1]=temp;
	return?i+1;
}

/*
	函數(shù)名：Count
	作用：統(tǒng)計數(shù)組中與x相等的元素的個數(shù)并返回
*/
int?Count（int?a[]int?xint?pint?r）
{
	int?count=0;
	for（int?i=p;i	{
		if（a[i]==x）
			count++;
	}
	return?count;
}

/*
	函數(shù)名：Modal
	作用：通過分治法得到數(shù)組的眾數(shù)和該眾數(shù)的重數(shù)
*/
void?Modal（int?a[]int?pint?r）
{
	if（p	{
		int?q=Partition（apr）;
		//統(tǒng)計分解法的主元出現(xiàn)的個數(shù)
		int?temp=Count（aa[q]pq+1）;
		if（multiplicity		{
			multiplicity=temp;
			modalnumber=a[q];
		}
		//如果該元素以左的個數(shù)大于重數(shù)，向左遞歸
		if（q-p-multiplicity>multiplicity）
			Modal（apq）;
		//如果該元素以右的個數(shù)大于重數(shù)，向右遞歸
		else?if（r-q-1>multiplicity）
			Modal（aq+1r）;
	}
}

int?main（）
{
	int?num[M]t