使用合并排序对数组进行排序

我已经在c中实现了合并排序,虽然代码似乎是正确的,代码没有给我排序的数组而是返回给它的相同数组,这意味着我的合并函数不工作

#include #include void re_sort(int arr[],int size); void merge(int left[],int right[],int arr[],int rightlen,int leftlen); int main(void) { int a[10]; int n; printf("enter the number\n"); scanf("%d",&n); printf("enter the elements\n"); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } re_sort(a,n); //merge sort using recursion printf("the sorted list is:\n"); for(int i=0;i<n;i++) { printf("%d\t",a[i]); } return 0; } void re_sort(int arr[],int size) { int mid,*left,*right; int k=0; if(size<2) return; else mid=size/2; left=(int*)(malloc(mid*(sizeof(int)))); // two sub arrays left and right right=(int*)(malloc((size-mid)*(sizeof(int)))); for(int i=0;i<mid;i++) { left[i]=arr[k++]; } for(int j=0;j<(size-mid);j++) { right[j]=arr[k++]; } re_sort(left,mid); //recursion until size becomes less than 2 re_sort(right,size-mid); merge(left,right,arr,size-mid,mid); //both the elements in left and right are merged } void merge(int left[],int right[],int arr1[],int rightlen,int leftlen) { int arr[100]; int k=0,i=0,j=0; while(i<leftlen && j<rightlen) { if(left[i]<= right[j]) arr[k++]=left[i++]; else arr[k++]=right[j++]; } while(i<leftlen) { arr[k++]=left[i++]; } while(j<rightlen) { arr[k++]=right[j++]; } for(int l=0;l<(rightlen+leftlen);l++) { arr1[l]=arr[l]; } free(left); free(right); } 

这里

  if(left[i]<= right[j]) arr[k++]=left[i++]; else arr[k++]=left[j++]; 

最后left应该是right

无论如何,你在哪里free摩托车的记忆......?

在每次递归调用时为每个子数组malloc一个新的缓冲区是一个非常糟糕的主意。 请记住, malloc是非常昂贵的行动, free费用甚至远远超过malloc

递归拆分产生的子数组不重叠(合并结果跨越两个合并部分除外)。 因此,对于合并结果您一次不需要多个缓冲区, 并且该合并不会干扰任何其他合并(除了它是子范围的那些)。 因此,只需创建整个输入数组的单个副本 ,并使用这两个数组作为递归合并的源位置和目标位置:

 void merge( int dst[], int src[], int idx1, int idx2, int end2) { int idx = idx1; int end1 = idx2; while(idx1 < end1 && idx2 < end2) dst[idx++] = src[idx1] <= src[idx2] ? src[idx1++] : src[idx2++]; while(idx1 < end1) dst[idx++] = src[idx1++]; while(idx2 < end2) dst[idx++] = src[idx2++]; } void mrgsrt( int dst[], int src[], int begin, int len) { if(len == 1) dst[begin] = src[begin]; if(len > 1) { int mid = len/2; mrgsrt(src, dst, begin, mid); mrgsrt(src, dst, begin+mid, len-mid); merge(dst, src, begin, begin+mid, begin+len); } } void sort( int a[], int len) { int *tmp; if((tmp = malloc(len*sizeof(*a))) != NULL) { memcpy(tmp, a, len*sizeof(*a)); mrgsrt(a, tmp, 0, len); free(tmp); } }