使用合并排序对数组进行排序
我已经在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); } }