分析：
算法采用快速排序的思想，根据相等与不等进行两边划分，相等部分的计数器如果不大于n/2，则对不等部分递归求解。
实现：
#include "iostream.h"
#include "stdlib.h"
#include "time.h"
#define N 10
int master( int temp[], int start, int end );
void insert( int temp[], int inspos, int end, int ins );
void main()
{
//Test data:
cout << "Test:n = " << N << endl << endl;
cout << "The random Array below:" << endl;
srand( (unsigned)time( NULL ) );
int* temp = new int[N];
for( int i = 0; i < N; i++ )
{
temp[i] = (int)(((float)rand()/65535*4)+1);
cout << temp[i] << " ";
}
cout << endl << endl;
int masterNum = master( temp, 0, N );
if( masterNum == 0 )
{
cout << "There is no master number in the Array!" << endl;
}
else
{
cout << "There is a master_number in the Array!"<< endl;
}
}
int master( int temp[], int start, int end )
//函数的作用是递归方法求解是否有主元素，如果没有返回0，有的话返回主元素在集合中的个数；
{
if( start >= N / 2 )
{
return 0;
}
int k = 1;
int tempInt = temp[start];
for( int i = start + 1; i < end; i++ )
{
if( tempInt == temp[i] )
{
insert( temp, start + k, i, tempInt );
k++;
}
}
if( k > N / 2 )
{
return k;
}
else
{
return master( temp, start + k, end );
}
}
void insert( int temp[], int inspos, int end, int ins )
//数据移位运算，作为原运算；
{
for( int i = end; i > inspos; i-- )
{
temp[i] = temp[i-1];
}
temp[inspos] = ins;
}
算法时间复杂度分析：
由于本算法采用了与快速排序相同的方法，所以其时间复杂度与快速排序相同
O（nlogn）；
改进算法：
算法依据在一个集合中，删除两个不同的数，则集合的主元素保持不变，故我们可以 通过此原理来实现线性时间算法，算法复杂度为O（n）；
改进算法实现：
bool master( int temp[] )
{
int count = 1;
int seed = temp[0];
for( int i = 1; i < N; i++ )
{
if( temp[i] == seed )
{
count++;
}
else
{
if( count > 0 )
{
count--;
}
else
{
seed = temp[i];
}
}
}
count = 0;
for( i = 0; i < N; i++ )
{
if( temp[i] == seed )
{
count++;
}
}
if( count > N/2 )
{
return true;
}
else
{
return false;
}
}
