c - 归并排序 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 - 经典的off-by-1。这种错误是 C 代码中的约定是使下限包含在内而上限不包含的原因之一 - 减少 +1 和 -1 你需要做的，搞砸的机会更少。

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

修复:首先，分配last-i1+1 元素。第二，一开始就将k初始化为0，而不是i1。三、修改最终副本为

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