#include <iostream>
#include <time.h>
using namespace std;
//Mode是从QuickSort得到
void Mode(int *, int, int, int *);
int Partition(int *, int, int);
//top是下一个众数的下标,top-1是当前众数的下标
//top和Frequence是全局变量,任何一处的赋值都会改变他们的值
//全局变量不作为函数参数,而是在函数内部直接使用
static int top = 0;
//Frequence记录众数的重数
static int Frequence = 0;
int main()
{
//生成随机数组
int n = 15;
int * nData = new int [n];
srand(time(0));
for (int i=0;i<n;i++)
nData [i] = 1 + rand()%n; //随机域为[1,n];
//打印
cout << "随机数组:" << endl;
for(int j=0;j<n;j++)
cout << nData[j] << " ";
cout << endl;
//数组nVal存储众数的值,只在[0,top-1]位置存放众数,top-1之后无效
int * nVal = new int [n];
//求众数及重数
Mode(nData,0,n-1, nVal);
//输出
cout<<"众数: ";
for (int k=0;k<top;k++)
cout<<nVal[k]<<" ";
cout << endl;
cout << "重数: " << Frequence << endl;
delete [] nData;
delete [] nVal;
return 0;
}
//求数组nData的众数
void Mode(int * nData, int left, int right,int * nVal)
{
int X = nData[left];
if(left<right)
{
//将小于X的放于其左(未排序),大于X的放于其右(未排序),并返回X在数组中的最终位置。
int i = Partition(nData,left,right);
//统计X出现的次数
int T=0;
for(int j = left; j <= right; j++)
{
if(nData[j]==X)
T++;
}
if(T==Frequence)
{
nVal[top] = nData[i];
top++;
//Frequence = T;
}
else if (T>Frequence)
{
nVal[0] = nData[i];
top=1;
Frequence = T;
}
if((i-left)>=T)
Mode(nData,left,i-1,nVal);
if((right-i)>=T)
Mode(nData,i+1,right,nVal);
}
}
//将小于nData[left]的元素放在nData[left]左边,大于nData[left]的元素放在nData[left]右边
//并返回nData[left]的最终位置
//Partition()并没有进行排序,只是分区
int Partition(int * nData, int left, int right)
{
int i=left, j=right+1;
int x = nData[left];
while(true)
{
while(nData[++i] < x);
while(nData[--j] > x);
if(i >= j) break;
int temp = nData[i];
nData[i] = nData[j];
nData[j] = temp;
// Swap(nData[i],nData[j]);
}
nData[left] = nData[j];
nData[j] = x;
return j;
}