何谓主元素？具体讲，如果一个数组A[1..n]中超过半数的元素都相同时，该数组被称为含有一个主元素。
(a) 设计一个有效算法，确定该数组中是否含有一个主元素，如果有，找出这个元素。
(b) 能否给出一个线性时间算法？
注意，该数组的元素之间可能不存在顺序——即不能进行”A[i]<A[j]”的大小判断，但是可以进行是否相等的判断。
普通的算法即需要2个for循环，算出每个数字的个数，这比较简单，这里不再给出，时间复杂度为O(n^2)。
下面给出一个时间复杂度为线性O(n)，基于分治法的线性时间求主元素算法。
算法思想
中位数：数列排序后位于最中间的那个数。如果一个数列有主元素,那么必然是其中位数。求一个数列有没有主元素，只要看中位数是不是主元素。
找中位数的方法:选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。
此时，划分元素所在位置为k。如果k>n/2，那么继续用同样的方法在左边部分找；如果k<n/2就在右边部分找；k=n/2就找到了中位元素。
根据快速排序的思想，可以在平均时间复杂度为O(n)的时间内找出一个数列的中位数。然后再用O(n)的时间检查它是否是主元素。 。
C语言源码如下：
{
int pivotkey = a[low];
while(low<high)
{
if(low<high && a[high]>=pivotkey)
-high;
a[low]=a[high];
if(low<high && a[low]<=pivotkey) ++low;
a[high]=a[low];
}
a[low]=pivotkey;
return low;
}
//快排
void quick_sort(int a[],int low,int high)
{
if(low<high)
{
int position = partition(a,low,high);
if(position>n/2)
quick_sort(a,low,position-1);
else if(position<n/2)
quick_sort(a,position+1,high);
else
mid=a[position];//找到中位数
}
}
int main()
{
int a[100];
printf("请输入个数n\n");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
a[i]=0;//初始化
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
quick_sort(a,1,n);
int count=0;
for(int i=1;i<=n;i++)//中位数个数
{
if(a[i] == mid)
count++;
}
if(count > n / 2)
printf("有主元素为 %d 出现了 %d 次\n",mid,count);
else
printf("无主元素\n");
system("pause");
}
