- 科技
- 归并排序noj
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 10000
void MergeSort1(int a
[],int n
);
void MergePass(int a
[],int length
,int n
);
void Merge(int *a
,int low
,int mid
,int high
);
void output(int a
[],int n
);
int main()
{
int a
[MAXSIZE
];
int n
;
int i
;
scanf("%d",&n
);
for(i
= 0; i
< n
; i
++){
scanf("%d",&a
[i
]);
}
MergeSort1(a
,n
);
output(a
,n
);
return 0;
}
void output(int a
[],int n
)
{
int i
;
for(i
= 0; i
< n
; i
++){
printf("%d\n",a
[i
]);
}
}
void MergeSort1(int a
[],int n
)
{
int length
;
for(length
= 1;length
< n
;length
= 2*length
){
MergePass(a
,length
,n
);
}
}
void MergePass(int a
[],int length
,int n
)
{
int i
;
for(i
= 0; i
+ 2*length
- 1 < n
; i
= i
+ 2*length
){
Merge(a
,i
,i
+ length
- 1,i
+ 2*length
- 1);
}
if(i
+length
-1 < n
){
Merge(a
,i
,i
+ length
- 1,n
-1);
}
}
void Merge(int *a
,int low
,int mid
,int high
)
{
int *tmp
;
int i
=low
,j
=mid
+1,k
=0;
int m
;
tmp
=(int *)malloc((high
-low
+1)*sizeof(int));
while(i
<=mid
&&j
<=high
){
if(a
[i
]<=a
[j
]){
tmp
[k
]=a
[i
];
i
++;
k
++;
}
else{
tmp
[k
]=a
[j
];
j
++;
k
++;
}
}
while(i
<=mid
){
tmp
[k
]=a
[i
];
i
++;
k
++;
}
while(j
<=high
){
tmp
[k
]=a
[j
];
j
++;
k
++;
}
for(k
=0,i
=low
;i
<=high
;k
++,i
++){
a
[i
]=tmp
[k
];
}
free(tmp
);
}
Processed:
0.011, SQL:
8
