c - 归并排序间隔递归

Question

以下代码应该对大小为:NX2 的二维数组进行排序

第一列代表坐标x。第二个代表坐标 y。

条件如下:

如果c>d:[c,a]>[d,b]

如果c=d 且a>b:[c,a]>[d,b]

我认为我在调用函数 memcopy 时出现了错误。但我不知道为什么。

void sort_intervals(int** intervals, int n)
{
    int **temp_arr = (int **)malloc(n * sizeof(int*));
    for(int i=0;i<n;i++)
    {
        temp_arr[i] = (int*) malloc(2*sizeof(int));
    }
    msort(intervals,n,temp_arr);
        for(int i=0;i<n;i++)
    {
        free(temp_arr[i]);
    }
    free(temp_arr);
}

void msort(int** intervals, int n,int** helper_array)
{
    int left = n / 2;
    int right = n-left;
    if (n < 2)
        return;
    msort(intervals, left, helper_array);
    msort(intervals + left, right, helper_array);
    merge(intervals, left, intervals + left, right, helper_array);
    memcpy(*intervals, *helper_array, n*sizeof(int*));
}

void merge(int** a,int a_length,int** b,int b_length,int** c)
{   int ia=0,ib=0,ic=0;
    while(ia<a_length && ib<b_length)
    {
       if(a[ia][0]<b[ib][0])
       {
           c[ic][0]=a[ia][0];
           c[ic][1]=a[ia][1];
           ia++;
       }

       else if(a[ia][0]>b[ib][0])
       {
           c[ic][0]=a[ib][0];
           c[ic][1]=a[ib][1];
           ib++;
       }
       else if(a[ia][0]==b[ib][0])
       {
           if(a[ia][1]>b[ib][1])
       {
           c[ic][0]=a[ib][0];
           c[ic][1]=a[ib][1];
           ib++;
       }
           else
       {
           c[ic][0]=a[ia][0];
           c[ic][1]=a[ia][1];
           ia++;
       }

       }

       ic++;

    }
    for(;ia<a_length;ia++,ic++)
    {
        c[ic][0]=a[ia][0];
        c[ic][1]=a[ia][1];
    }
    for(;ib<b_length;ib++,ic++)
    {
        c[ic][0]=a[ib][0];
        c[ic][1]=a[ib][1];
    }
}

Answer 1

memcpy 将不起作用，因为代码正在对数据而不是指针进行排序。您需要一个循环来复制 n 对整数。

a[ib][...] 的所有实例都需要更改为 b[ib][...]。

评论中指出的更改:

#include <malloc.h>
#include <stdio.h>

void msort(int** intervals, int n,int** helper_array);
void merge(int** a,int a_length,int** b,int b_length,int** c);

void sort_intervals(int** intervals, int n)
{
int **temp_arr = (int **)malloc(n * sizeof(int*));\
int i;                                  /* c not c++ */
    for(i=0;i<n;i++)                    /* c not c++ */
    {
        temp_arr[i] = (int*) malloc(2*sizeof(int));
    }
    msort(intervals,n,temp_arr);
    for(i=0;i<n;i++)                    /* c not c++ */
    {
        free(temp_arr[i]);
    }
    free(temp_arr);
}

void msort(int** intervals, int n,int** helper_array)
{
    int left = n / 2;
    int right = n-left;
    int i;                              /* fix */
    if (n < 2)
        return;
    msort(intervals, left, helper_array);
    msort(intervals + left, right, helper_array);
    merge(intervals, left, intervals + left, right, helper_array);
    for(i = 0; i < n; i++)              /* fix */
    {
        intervals[i][0] = helper_array[i][0];
        intervals[i][1] = helper_array[i][1];
    }
}

void merge(int** a,int a_length,int** b,int b_length,int** c)
{   int ia=0,ib=0,ic=0;
    while(ia<a_length && ib<b_length)
    {
       if(a[ia][0]<b[ib][0])
       {
           c[ic][0]=a[ia][0];
           c[ic][1]=a[ia][1];
           ia++;
       }
       else if(a[ia][0]>b[ib][0])
       {
           c[ic][0]=b[ib][0];           /* fix */
           c[ic][1]=b[ib][1];           /* fix */
           ib++;
       }
       else if(a[ia][1]>b[ib][1])       /* clean up */
       {
           c[ic][0]=b[ib][0];           /* fix */
           c[ic][1]=b[ib][1];           /* fix */
           ib++;
       }
       else
       {
           c[ic][0]=a[ia][0];
           c[ic][1]=a[ia][1];
           ia++;
       }
       ic++;
    }
    for(;ia<a_length;ia++,ic++)
    {
        c[ic][0]=a[ia][0];
        c[ic][1]=a[ia][1];
    }
    for(;ib<b_length;ib++,ic++)
    {
        c[ic][0]=b[ib][0];              /* fix */
        c[ic][1]=b[ib][1];              /* fix */
    }
}

int main()
{
int a[8][2] = {{7,5},{3,4},{1,2},{1,1},{7,3},{2,2},{3,5},{2,3}};
int *pa[8] = {a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]};
int i;

    sort_intervals(pa, sizeof(pa)/sizeof(pa[0]));
    for(i = 0; i < sizeof(pa)/sizeof(pa[0]); i++)
        printf("%1d %1d\n", pa[i][0], pa[i][1]);
    return 0;
}

或者您可以对指针进行排序:

#include <malloc.h>
#include <memory.h>
#include <stdio.h>

void msort(int** intervals, int n,int** helper_array);
void merge(int** a,int a_length,int** b,int b_length,int** c);

void sort_intervals(int** intervals, int n)
{
    int **temp_arr = (int **)malloc(n * sizeof(int*));
    msort(intervals,n,temp_arr);
    free(temp_arr);
}

void msort(int** intervals, int n,int** helper_array)
{
    int left = n / 2;
    int right = n-left;
    if (n < 2)
        return;
    msort(intervals, left, helper_array);
    msort(intervals + left, right, helper_array);
    merge(intervals, left, intervals + left, right, helper_array);
    memcpy(intervals, helper_array, n*sizeof(int*));
}

void merge(int** a,int a_length,int** b,int b_length,int** c)
{
int ia=0,ib=0,ic=0;
    while(ia<a_length && ib<b_length)
    {
       if(a[ia][0] < b[ib][0])
           c[ic] = a[ia++];
       else if(a[ia][0] > b[ib][0])
           c[ic] = b[ib++];
       else if(a[ia][1] <= b[ib][1])
           c[ic] = a[ia++];
       else
           c[ic] = b[ib++];
       ic++;
    }
    while(ia < a_length)
        c[ic++] = a[ia++];
    while(ib < b_length)
        c[ic++] = b[ib++];
}

int main()
{
int a[8][2] = {{7,5},{3,4},{1,2},{1,1},{7,3},{2,2},{3,5},{2,3}};
int *pa[8] = {a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]};
int i;

    sort_intervals(pa, sizeof(pa)/sizeof(pa[0]));
    for(i = 0; i < sizeof(pa)/sizeof(pa[0]); i++)
        printf("%1d %1d\n", pa[i][0], pa[i][1]);
    return 0;
}

此序列适用于两种情况:

int main()
{
int a[5][2] = {{-1,10},{0,9},{1,7},{2,3},{3,4}};
int *pa[5] = {a[0],a[1],a[2],a[3],a[4]};
int i;

    sort_intervals(pa, sizeof(pa)/sizeof(pa[0]));
    for(i = 0; i < sizeof(pa)/sizeof(pa[0]); i++)
        printf("%3d %3d\n", pa[i][0], pa[i][1]);
    return 0;
}

对于排序数据(而不是排序指针)示例，可以对所有数据使用单个分配，而不是n 分配。对于这种特定情况，代码可以使用 temp_arr[0] (或 *temp_arr)而不是 temp_bfr 来分配和释放数据空间，但使用 temp_bfr 是一种更通用的执行此操作的方法，如果 temp_arr 已排序或另有修改。

void sort_intervals(int** intervals, int n)
{
/* allocate space for array of pointers */
int **temp_arr = (int **)malloc(n * sizeof(int*));
/* allocate space for data */
int *temp_bfr  = (int *)malloc(n * 2 * sizeof(int));
int i;
    for(i=0;i<n;i++)
        temp_arr[i] = temp_bfr + 2*i;
    msort(intervals,n,temp_arr);
    free(temp_bfr);                     /* free data space */
    free(temp_arr);                     /* free array of pointer space */
}