内容发布更新时间 : 2025/5/6 2:40:09星期一 下面是文章的全部内容请认真阅读。
合并排序1: #include
void input(int a);
void merge(int arrayc[],int arrayd[],int l,int m,int r); void mergepass(int arrayx[],int arrayy[],int s); void mergesort(int array1[]); void diaplay(int a); };
void list::input(int a) {
cout<<\ for(int i=0;i>array[i]; }
void list::merge(int arrayc[],int arrayd[],int l,int m,int r) {
int i=l; int j=m+1; int k=l;
while((i<=m)&&(j<=r)) if(arrayc[i]<=arrayc[j]) arrayd[k++]=arrayc[i++]; else arrayd[k++]=arrayc[j++]; if(i>m) for(int q=j;q<=r;q++)
arrayd[k++]=arrayc[q];
else
for(int q=i;q<=m;q++) arrayd[k++]=arrayc[q];
} void list::mergepass(int arrayx[],int arrayy[],int s)
{ int i=0; while(i<=N-2*s) {
merge(arrayx,arrayy,i,i+s-1,i+2*s-1); i=i+2*s;
}
1
if((i+s)
merge(arrayx,arrayy,i,i+s-1,N-1); else for(int j=i;j
void list::mergesort(int array1[])
{ int array2[N];
int s=1;
while(s
mergepass(array1,array2,s); s+=s;
mergepass(array2,array1,s); s+=s; } }
void list::diaplay(int a) {
for(int i=N-a;i
void main() {
list f; int a;
cout<<\请输入要合并排序的数组大小:(数组最大上限 100)\ cin>>a; f.input(a);
f.mergesort (f.array); f.diaplay (a); }
合并排序:2 #include
usingnamespace std;
void MERGES(int *A,int p,int q,int r) //下标 P<=q
int n1=q-p+1; //n1:p,q之间的数的个数
int n2=r-q; //n2:q以后到r的数的个数
int *L=newint [n1+1], //动态申请两个子数组 *R=newint [n2+1];
2
int i,j,k;
for (i=0;i
R[j]=A[q+j]; }
L[n1]=10000; //设置哨兵 R[n2]=10000; i=0;
j=0;
for (k=p-1;k
if (L[i]<=R[j])
{ A[k]=L[i]; i=i+1; }
else
{ A[k]=R[j]; j=j+1; } } }
void MERGESORT(int *A,int p,int r) { if (p
MERGESORT(A,p,q); MERGESORT(A,q+1,r); MERGES(A,p,q,r); } }
void main() {
int x,z,p,r;
cout<<\请输入数组长度\ cin>>x; int *A= newint[x];
cout<<\请输入数组的元素\
3