3_2.rar_4 3 2 1_主元素_主元素的判定_分治 主元素

#include "stdio.h" void swap(int *x,int *y) //交换元素x,y { int t; t=*x; *x=*y; *y=t; } int partition(int T[],int q,int p,int x) //将<x的元素交换到左边区域,将>x的元素交换到右边区域 { int i=q,j=p+1,t; for(;i<j;i++) if(T[i]==x) { t=i; break; } i=q; while(1) { while(T[--j]>x); while((i<j)&&T[++i]<=x); if(i>=j)break; swap(&T[i],&T[j]); } swap(&T[t],&T[j]); return j; } void QuickSort(int T[],int q,int p) { int z; if(q<p) { z=partition(T,q,p,T[q]); QuickSort(T,q,z-1);//对左半段排序 QuickSort(T,z+1,p);//对右半段排序 } } int Select(int T[],int q,int p,int k) { int x,s,j,num,c,d,i; if(p-q<5) { QuickSort(T,q,p); return T[q+k-1]; } for(i=0;i<=(p-q-4)/5;i++) { int s=q+5*i,t=s+4; QuickSort(T,s,t); swap(&T[q+i],&T[s+2]); } x=Select(T,q,q+(p-q-4)/5,(p-q-4)/10);//找中位数的中位数 s=partition(T,q,p,x); j=s-q+1; num=0; c=s,d=0; while(c>d) //将与x相等的元素集中在一起。 { while(T[c--]==x); while(c>d&&T[d++]!=x); swap(&T[d-1],&T[c+1]); } for(d=0;d<=j;d++) if(T[d]==x) num++; s=s-num+1; j=s-q+1; if(num>=1) { if((j<=k)&&(k<=j+num-1)) return T[s]; else return Select(T,s+num+1,p,k-j-num); } else if(k<=j) return Select(T,q,s,k); else return Select(T,s,p,k-j); } int checkMaster(int T[],int q,int p) { int t=Select(T,q,p,(p-q+2)/2); int num=0; int i; for(i=q;i<=p;i++) { if(T[i]==t) num++; } if(num>(p-q+2)/2) return t; else return 0; } void main(void) { int T[16]={1,2,2,2,3,4,3,2,2,4,2,2,6,7,2,2},Master; Master=checkMaster(T,0,sizeof(T)/sizeof(int)-1); if(Master==0) printf("该数组不存在主元素"); else printf("该数组的主元素为%d\n",Master); }