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

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

/*
	函數(shù)名：Partition
	作用：對(duì)數(shù)組進(jìn)行分解（與快速排序的分解思想類(lèi)似）
*/
int?Partition（int?a[]int?pint?r）
{
	//在a[p]到a[r-1]中隨機(jī)選擇一個(gè)元素作為主元
//	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)計(jì)數(shù)組中與x相等的元素的個(gè)數(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
	作用：通過(guò)分治法得到數(shù)組的眾數(shù)和該眾數(shù)的重?cái)?shù)
*/
void?Modal（int?a[]int?pint?r）
{
	if（p	{
		int?q=Partition（apr）;
		//統(tǒng)計(jì)分解法的主元出現(xiàn)的個(gè)數(shù)
		int?temp=Count（aa[q]pq+1）;
		if（multiplicity		{
			multiplicity=temp;
			modalnumber=a[q];
		}
		//如果該元素以左的個(gè)數(shù)大于重?cái)?shù)，向左遞歸
		if（q-p-multiplicity>multiplicity）
			Modal（apq）;
		//如果該元素以右的個(gè)數(shù)大于重?cái)?shù)，向右遞歸
		else?if（r-q-1>multiplicity）
			Modal（aq+1r）;
	}
}

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