这是我的用于合并排序的代码,但是此代码输出错误的答案,我已经检查了好几次,但找不到错误的输出原因。如果有人能告诉我为什么会发生,我将不胜感激。
#include<bits/stdc++.h>
using namespace std;
void merge(int a[],int l,int m,int h){
int n1=m-l+1;
int n2=h-m;
int L[n1],R[n2];
int i,j,k;
for( i=0;i<n1;i++){
L[i]=a[l+i];
}
for(j=0;j<n2;j++){
R[j]=a[m+1+j];
}
i=0;j=0;k=0;
while(i<n1 && j<n2){
if(L[i]<R[j]){
a[k]=L[i];
i++;
}else{
a[k]=R[j];
j++;
}
k++;
}
while(i<n1){
a[k]=L[i];
i++;
k++;
}
while(j<n2){
a[k]=R[j];
k++;
j++;
}
}
void mergesort(int a[],int l,int h){
if(l<h){
int mid=l+(h-l)/2;
mergesort(a,l,mid);
mergesort(a,mid+1,h);
merge(a,l,mid,h);
}}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main(){
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergesort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
输入:
5
5 4 3 2 1
输出:
给出数组是5 4 3 2 1
排序数组是1 2 1 2 5
您在k
中用错误的值初始化了merge
。
[k=0;
会将指针保留在开头,而是使用k=l;
开始将值复制到当前合并段的左边界。
void merge(int a[],int l,int m,int h){
int n1=m-l+1;
int n2=h-m;
int L[n1],R[n2];
int i,j,k;
for( i=0;i<n1;i++){
L[i]=a[l+i];
}
for(j=0;j<n2;j++){
R[j]=a[m+1+j];
}
i=0;j=0;k=l;
while(i<n1 && j<n2){
if(L[i]<R[j]){
a[k]=L[i];
i++;
}else{
a[k]=R[j];
j++;
}
k++;
}
while(i<n1){
a[k]=L[i];
i++;
k++;
}
while(j<n2){
a[k]=R[j];
k++;
j++;
}
}