使用分治法解决众数问题

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

/*modalnumber用来表示众数*/
int modalnumber=0;
/*multiplicity用来表示该众数的重数*/
int multiplicity=0;

/*
	函数名：Partition
	作用：对数组进行分解（与快速排序的分解思想类似）
*/
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;
}

/*
	函数名：Count
	作用：统计数组中与x相等的元素的个数并返回
*/
int Count（int a[]int xint pint r）
{
	int count=0;
	for（int i=p;i	{
		if（a[i]==x）
			count++;
	}
	return count;
}

/*
	函数名：Modal
	作用：通过分治法得到数组的众数和该众数的重数
*/
void Modal（int a[]int pint r）
{
	if（p	{
		int q=Partition（apr）;
		//统计分解法的主元出现的个数
		int temp=Count（aa[q]pq+1）;
		if（multiplicity		{
			multiplicity=temp;
			modalnumber=a[q];
		}
		//如果该元素以左的个数大于重数，向左递归
		if（q-p-multiplicity>multiplicity）
			Modal（apq）;
		//如果该元素以右的个数大于重数，向右递归
		else if（r-q-1>multiplicity）
			Modal（aq+1r）;
	}
}

int main（）
{
	int num[M]t