c - 结构体的合并排序

Question

#include<stdio.h>
#include<stdlib.h>
typedef struct points{
        float axis[2];
        int id;
}Points;

typedef enum{
        SortById,
        SortByXAxis
}SortType;

Points* fill_Array(char* filename, int* length);
void Print_set(Points* set, int number_of_points);
void mergesort(Points* set, int low, int high, int number_of_points,SortType sort);
void merge(Points* set, int low, int middle, int high, int number_of_points,SortType sort);

int main(int argc, char* argv[])
{
    int length;
    Points *array;
    array=fill_Array(argv[1],&length);
    Print_set(array,length);
    printf("\n\n");
    mergesort(array,0,length,length,SortById);
    Print_set(array,length);
    return 0;
}
Points* fill_Array(char* filename,int* length)
{
    int i;
    Points* array;
    FILE* file=fopen(filename,"r");

    if(file == NULL)
    {
        return NULL;
    }

    fscanf(file,"%d",length);
    array=malloc(sizeof(Points)* *length);

    for(i = 0; i < *length; i++)
    {
        fscanf(file,"%d %f %f", &(array+i)->id,&(array+i)->axis[0],&(array+i)->axis[1]);
    }
    fclose(file);

    return array;
}

void Print_set(Points *set, int number_of_points)
{
    int i;

    for(i = 0; i < number_of_points; i++)
    {
        printf("%d %f %f\n",(set+i)->id,(set+i)->axis[0],(set+i)->axis[1]);
    }
}

void mergesort(Points* set,int low,int high,int number_of_points, SortType sort)
{
    int mid1;

    if((high-low)>=1)
    {
        mid1 = (low+high)/2;

        mergesort(set, low, mid1, number_of_points, sort);
        mergesort(set, mid1+1, high, number_of_points, sort);
        merge(set, low, mid1, high, number_of_points, sort);

    }

}
void merge(Points* set, int low, int middle, int high, int number_of_points, SortType sort)
{
        int leftIndex=low;
        int rightIndex=middle;
        int combinedIndex = low;
        Points tempArray[number_of_points];
        int i;

        while(leftIndex <= middle && rightIndex<= high)
        {
            if(set[leftIndex].id <= set[rightIndex].id)
            {
                tempArray[combinedIndex++] = set[leftIndex++];
            }
            else
                tempArray[combinedIndex++] = set[rightIndex++];
        }

        if(leftIndex == middle+1)
        {
            while(rightIndex <= high)
            {
                tempArray[combinedIndex++] = set[rightIndex++];
            }
        }
        else
        {
            while(leftIndex <= middle)
            {
                tempArray[combinedIndex++] = set[leftIndex++];
            }
        }

        for( i = low; i < high; i++)
        {
            set[i] = tempArray[i];
        }
}

我正在尝试使用自定义合并排序函数对输入文件执行合并排序。然而，合并排序函数不起作用并在下面打印出来，第一个 block 是打印出来的实际输入文件，以确保 fscanf 正确读取所有内容，第二个 block 是运行合并函数后的打印。这些函数复制了一些值，也不对它们进行排序，我在代码中找不到错误。请注意，枚举将用于对 id 或第一个浮点值进行排序，我只是想在使用它对 id 或这些值进行排序之前让合并排序发挥作用。

1 13.000000 7.000000
13 14.000000 6.000000
95 7.000000 13.000000
39 0.000000 20.000000
78 10.000000 10.000000
68 3.000000 17.000000
32 6.000000 14.000000
10 19.000000 1.000000
0 18.000000 2.000000
45 17.000000 3.000000
92 4.000000 16.000000
29 5.000000 15.000000
85 8.000000 12.000000
79 15.000000 5.000000
12 16.000000 4.000000
32 1.000000 19.000000
77 9.000000 11.000000
52 12.000000 8.000000
80 11.000000 9.000000
31 2.000000 18.000000


1 13.000000 7.000000
13 14.000000 6.000000
68 3.000000 17.000000
0 18.000000 2.000000
10 19.000000 1.000000
0 18.000000 2.000000
0 18.000000 2.000000
92 4.000000 16.000000
92 4.000000 16.000000
29 5.000000 15.000000
32 1.000000 19.000000
52 12.000000 8.000000
77 9.000000 11.000000
79 15.000000 5.000000
12 16.000000 4.000000
32 1.000000 19.000000
32 1.000000 19.000000
80 11.000000 9.000000
95 7.000000 13.000000
95 7.000000 13.000000

Answer 1

您似乎对边界索引的含义感到困惑。考虑对函数 mergesort() 的初始调用:

    mergesort(array,0,length,length,SortById);

您为参数传递相同的值 high和number_of_points ，这很好，但这意味着 high表示排序范围索引的独占上限。 mergesort()然而，实现似乎适合争论high表示包含边界。

您的 merge() 仍然令人困惑。函数，这可能是这里的罪魁祸首。通过将传递的中点值作为右子数组的起始索引，似乎期望中点作为左子数组的独占上限，但当前的 mergesort()实现通过了包含上限。另一方面，merge()执行的一些索引比较仅当 middle 时才合适是子数组的包含上限。

简而言之，你一头雾水。该算法的基本轮廓看起来不错，但您需要决定(并自己记录)函数参数代表什么，并将实现细节与此相协调。如果我是你，我会对所有区间采用半开表示，以便下限始终包含在内，上限始终排除。除此之外，这样做的优点是每个中点值都可以同样正确地解释为其子数组左半部分的(不包括)上限或右半部分的(包括)下界。