mergesort C实现

Question

我在遵循mergesort算法的Xcode上用C语言编写了这段代码.问题是,有时我得到EXC_BAD_ACCESS,我无法管理错误的位置!合并算法应该工作(我在mergesort函数之外尝试它并且工作!).感谢您的帮助和耐心!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 6

void mymerge (int v[], int i1,int i2, int last); //mergesort core: merge two ordinated arrays in one bigger ordinated array
void mymergesort (int v[], int lower, int upper);//mergesort
void printv (int v[],int lower, int upper);

int main () {
    int i;
    srand((unsigned int)time(NULL));
    int v[DIM];
    for (i=0; i<DIM; i++)
        v[i]=rand()%15;
    printv(v, 0, DIM-1);
    getc(stdin);
    mymergesort(v, 0, DIM-1);
    printv(v, 0, DIM-1);
}
void printv (int v[],int lower, int upper){
    int i;
    for (i=lower; i<=upper; i++)
    printf("%d\t",v[i]);
}
void mymergesort (int v[], int lower, int upper){
    int mid=(upper+lower)/2;
    if (upper<lower) {
        mymergesort(v, lower, mid);
        mymergesort(v, mid+1, upper);
        mymerge(v,lower,mid+1,upper);
    }
}
void mymerge (int v[], int i1,int i2, int last){
    int i=i1,j=i2,k=i1,*vout;
    vout=(int*)malloc((last-i1+1)*sizeof(int));
    while (i<i2 && j<=last) {
        if (v[i]<=v[j]) {
            vout[k++]=v[i++];
        }else {
            vout[k++]=v[j++];
        }
    }
    for (;i<i2;i++) vout[k++]=v[i];
    for (;j<=last;j++) vout[k++]=v[j];
    for (k=i1; k<=last; k++) v[k]=vout[k];
free(vout);
}

编辑:非常感谢!但我认为还有另一个问题,当我尝试排序一个更大的数组(200个元素)时,程序不起作用(我得到一个malloc错误:释放对象的错误校验和 - 对象可能在被释放后被修改).但是,如果我从xCode调试器运行它一切正常

Answer 1

这:vout=(int*)malloc((last-i1)*sizeof(int));错了.

首先,你想要的元素数量last-i1+1不是last-i1- 经典的1分.这种错误是原因为什么在C代码的惯例是让下界包容和上界独家一个-少+1而-1你需要做的,少给搞砸了机会.

更严重的错误是您vout从索引开始i1.如果你这样做,你需要分配last+1元素vout,你永远不会使用第一个i1(索引0 .. i1-1).

修复:首先,分配last-i1+1元素.其次,k在开始时初始化为0,而不是i1.第三,改变最终副本

for (k=i1; k<=last; k++) v[k] = vout[k-i1];